【題目】 兩個單向連結清單相交的一系列問題
在本題中，單連結清單可能有環，也可能無環。給定兩個單連結清單的頭節點 head1和head2，這兩個連結清單可能相交，也可能不相交。請實作一個函數， 如果兩個連結清單相交，請傳回相交的第一個節點；如果不相交，傳回null 即可。
【要求】
如果連結清單1的長度為N，連結清單2的長度為M，時間複雜度請達到 O(N+M)，額外空間複雜度請達到O(1)。
【分析】
本題目可以拆分為：
問題1.如何判斷單連結清單有環還是無環，有環傳回第一個入環節點，無環傳回null
第一種方法
可以利用哈希表（hashSet）：周遊每一個節點，想要把每個結點都存放到哈希表中；但是哈希表中已經存過的節點就存不進去了（第一個不能存入哈希表的節點就是第一個入環的節點）。
注：需要一個哈希表，空間複雜度O(n)不滿足。
第二種方法
設定兩個指針：一個快指針（走兩步），一個慢指針（走一步）；當快指針和慢指針相遇的時候，快指針回到頭結點的位置，和慢指針一起以一步的步幅走，相遇的節點就是第一個入環節點。
【代碼實作】
//1.定義結點的結構
public static class Node{
int value;
Node next;
public Node(int data) {
this.value=data;
}
}
//2.判斷有環還是無環的方法，傳回第一個入環節點
public static Node getLoopNode(Node head) {
//2.1小于三個結點肯定構不成環
if(head==null||head.next==null||head.next.next==null) {
return null;
}
//2.2快指針和慢指針移動找相遇的節點
Node n1=head.next;//n1是慢指針
Node n2=head.next.next;//n2是快指針
while(n1!=n2) {
if(n2.next==null||n2.next.next==null) {
return null;//走到末尾了也沒相交，就是無環
}
n2=n2.next.next;
n1=n1.next;
}
//2.3兩個節點相遇，快指針回到頭，和慢指針一起以一步的步幅走，相遇的就是第一個的入環節點
n2=head;
while(n1!=n2) {
n1=n1.next;
n2=n2.next;
}
return n1;
}
問題2.兩個無環連結清單怎麼找到第一個相交的節點
結構示意圖
第一種方法
利用哈希表：
周遊第一個連結清單，把所有的節點都存入到哈希表中（因為是無環連結清單，是以一定可以存進去）（哈希表中存放的節點的記憶體位址，和節點的值沒有關系）；周遊第二個連結清單的節點，每周遊一個檢視哈希表中是否已經有了這個節點，哈希表中第一個存不進去的節點就是第一個相交節點。
哈希表空間複雜度是O(n)，不滿足題目要求。
第二種方法
1.先确定兩個連結清單的長度差
2.兩個連結清單在移動的過程中，如果相交了（根據連結清單的特殊性，隻有一個next指針，隻能連接配接一個下一個結點，是以第一個公共結點之後，隻知道連結清單的結尾都是相同的）（變量中存放的是記憶體位址，和資料無關），那麼末尾的記憶體位址一定是相同的
3.如果最後的相等，那麼說明是有相交的節點的，但是不一定是最後一個。
4.讓長的節點從頭開始，先走距離差個距離；短的從頭開始走，相等的就是他們相交的節點
【代碼實作】
public static Node noLoop(Node head1,Node head2) {
//1.如果有一個為空連結清單，那麼一定沒有相交結點
if(head1==null||head2==null) {
return null;
}
//2.兩個連結清單中的節點分别往下走，走到末尾确定他們的長度差
Node cur1=head1;
Node cur2=head2;
int n=0;
while(cur1.next!=null){
n++;
cur1=cur1.next;
}
while(cur2.next!=null){
n--;
cur2=cur2.next;
}
//3.如果走到最後了，也沒有記憶體位址相同的節點，那麼就說明沒有相交的節點
if (cur1!=cur2) {
return null;
}
//4.确定那個連結清單是長連結清單cur1，那個是短連結清單cur2
//如果n>0,說明1比2長，那麼确定要往回走的連結清單是長的那個cur1；
cur1=n>0?head1:head2;
//如果長的連結清單是1，那麼cur2表示的就是短的連結清單，否則的話相反
cur2=cur1==head1?head2:head1;
//5.确定距離差
n=Math.abs(n);
//6.長的連結清單從頭開始先移動距離差個距離
while(n!=0) {
n--;
cur1=cur1.next;
}
//7.如果cur1不等于cur2 說明長連結清單中前n個結點是不相交的，兩個都一起移動，找到相等的點就是相交的點
while(cur1!=cur2) {
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}
問題3 一個有環連結清單和一個無環清單怎麼找到第一個相交的節點
可以得出結論就是這兩個連結清單不可能相交。
因為連結清單的特性決定了如果兩個連結清單相交的話，它們之後會一直相交下去，（相當于兩個連結清單是從屬關系，認為是一個連結清單了）。
無環的和有環的連結清單不能有公共的結點。
問題4 兩個有環連結清單怎麼找到第一個相交點
第一種情況：兩個環沒有任何關系，各自有各自的環
第二種情況：兩個連結清單相交之後共享同一個環（同一個入環節點就是這種結構）
第三種情況：兩個連結清單入環節點不一樣個，但是同樣共享一個環（不同的入環節點）
【思路】
1.調用問題1中找到入環節點的方法，找到兩個連結清單的入環點loop1和loop2；
2.用loop1和loop2表示每一個連結清單的入環點，如果相等表示入環點相等，那麼就是第二種情況；
找到相交點的步驟是：不考慮下面的環，然後是兩個無環連結清單找相交點的方法
3.loop1和loop2不相等，說明是第一種情況和第三種情況。
讓loop1不斷往下走，如果走回自己了，還沒碰到loop2，說明不是一個環，那麼就是第一種情況，沒有相交點；如果在走回自己的過程中，碰到了loop2，那麼說明是一個環，是第三種情況，傳回的是loop1還是loop2那個是相交點都對（隻是針對不同的連結清單來說的）
【代碼實作】
public static Node bothLoop(Node head1,Node head2,Node loop1,Node loop2) {
Node cur1=null;
Node cur2=null;
if (loop1==loop2) {
//如果是第二種結構，入環點相等，不考慮下面的環，就是無環清單找交點的方法（注意走到入環點即可）
cur1=head1;
cur2=head2;
int n=0;
while(cur1!=loop1) {
n++;
cur1=cur1.next;
}
while(cur2!=loop2) {
n--;
cur2=cur2.next;
}
cur1=n>0?head1:head2;
cur2=cur1==head1?head2:head1;
n=Math.abs(n);
while(n!=0) {
cur1=cur1.next;
n--;
}
if(cur1!=cur2) {
cur1=cur1.next;
cur2=cur2.next;
}
return cur1;
}else {
//loop1!=loop2是1或者3結構，讓loop1移動
cur1=loop1.next;
while(cur1!=loop1) {
if(cur1==loop2) {
return loop1;
}
cur1=cur1.next;
}
return null;
}
}
[整個流程方法]
//整個流程方法
public static Node getIntersectNode(Node head1,Node head2) {
if(head1==null||head2==null) {
return null;
}
//第一步判斷有環還是無環
Node loop1=getLoopNode(head1);
Node loop2=getLoopNode(head2);
//第二步兩個無環怎麼判斷交點
if(loop1==null&&loop2==null) {
return noLoop(head1, head2);
}
//第三步兩個有環怎麼判斷交點
if(loop1!=null&&loop2!=null) {
return bothLoop(head1, head2, loop1, loop2);
}
return null;
}