題目：給兩個單鏈表宇葱，如何判斷兩個單鏈表是否相交？若相交刊头，則找出第一個相交的節(jié)點黍瞧。
這道題的思路和解法有很多，在這把這道題的解法做一個詳細的總結(jié)原杂。
解這道題之前印颤，我們需要首先明確一個概念：
如果兩個單鏈表有共同的節(jié)點，那么從第一個共同節(jié)點開始穿肄，后面的節(jié)點都會重疊年局，直到鏈表結(jié)束。
因為兩個鏈表中有一個共同節(jié)點咸产，則這個節(jié)點里的指針域指向的下一個節(jié)點地址一樣矢否，所以下一個節(jié)點也會相交，依次類推脑溢。所以僵朗，若相交，則兩個鏈表呈“Y”字形。如下圖：
1.暴力解法验庙。
從頭開始遍歷第一個鏈表顶吮，遍歷第一個鏈表的每個節(jié)點時，同時從頭到尾遍歷第二個鏈表粪薛，看是否有相同的節(jié)點云矫，第一次找到相同的節(jié)點即第一個交點。若第一個鏈表遍歷結(jié)束后汗菜，還未找到相同的節(jié)點让禀，即不存在交點。時間復(fù)雜度為O(n^2)陨界。這種方法顯然不是寫這篇博客的重點巡揍。感帅。宗兼。不多說了劲绪。
2.使用棧憨栽。
我們可以從頭遍歷兩個鏈表。創(chuàng)建兩個棧卿嘲，第一個棧存儲第一個鏈表的節(jié)點捕传，第二個棧存儲第二個鏈表的節(jié)點鬼悠。每遍歷到一個節(jié)點時录淡，就將該節(jié)點入棧捌木。兩個鏈表都入棧結(jié)束后。則通過top判斷棧頂?shù)墓?jié)點是否相等即可判斷兩個單鏈表是否相交嫉戚。因為我們知道刨裆，若兩個鏈表相交，則從第一個相交節(jié)點開始彬檀，后面的節(jié)點都相交帆啃。
若兩鏈表相交，則循環(huán)出棧窍帝，直到遇到兩個出棧的節(jié)點不相同努潘，則這個節(jié)點的后一個節(jié)點就是第一個相交的節(jié)點。
node temp=NULL; //存第一個相交節(jié)點
while(!stack1.empty()&&!stack1.empty()) //兩棧不為空
{
temp=stack1.top();
stack1.pop();
stack2.pop();
if(stack1.top()!=stack2.top())
{
break;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
這個方法在沒有要求空間復(fù)雜度的時候坤学，使用棧來解決這個問題也是挺簡便的疯坤。
3.遍歷鏈表記錄長度。
同時遍歷兩個鏈表到尾部拥峦，同時記錄兩個鏈表的長度贴膘。若兩個鏈表最后的一個節(jié)點相同卖子，則兩個鏈表相交略号。
有兩個鏈表的長度后，我們就可以知道哪個鏈表長，設(shè)較長的鏈表長度為len1,短的鏈表長度為len2玄柠。
則先讓較長的鏈表向后移動(len1-len2)個長度突梦。然后開始從當前位置同時遍歷兩個鏈表，當遍歷到的鏈表的節(jié)點相同時羽利，則這個節(jié)點就是第一個相交的節(jié)點宫患。
代碼示例:
typedef struct node_t
{
int data;//data
struct node_t *next; //next
}node;
node* find_node(node *head1, node *head2)
{
//鏈表帶頭節(jié)點
if(head1==NULL || head2==NULL)
{
return NULL;//如果有為空的鏈表，肯定是不相交的
}
node *p1, *p2;
p1 = head1;
p2 = head2;
int len1 = 0;
int len2 =0;
int diff = 0;
while(p1->next!=NULL)
{
p1 = p1->next;
len1++;
}
while(p2->next!=NULL)
{
p2 = p2->next;
len2++;
}
if(p1 != p2) //如果最后一個節(jié)點不相同,返回NULL
{
return NULL;
}
diff = abs(len1 - len2);
if(len1 > len2)
{
p1 = head1;
p2 = head2;
}
else
{
p1 = head2;
p2 = head1;
}
for(int i=0; i<diff; i++)
{
p1 = p1->next;
}
while(p1 != p2)
{
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
這個方法也非常的簡便并且額外的空間開銷很小这弧。時間復(fù)雜度為O(len1+len2)娃闲。
4.哈希表法。
既然連個鏈表一旦相交匾浪，相交節(jié)點一定有相同的內(nèi)存地址皇帮，而不同的節(jié)點內(nèi)存地址一定是不同的，那么不妨利用內(nèi)存地址建立哈希表蛋辈，如此通過判斷兩個鏈表中是否存在內(nèi)存地址相同的節(jié)點判斷兩個鏈表是否相交属拾。具體做法是：遍歷第一個鏈表，并利用地址建立哈希表冷溶，遍歷第二個鏈表渐白，看看地址哈希值是否和第一個表中的節(jié)點地址值有相同即可判斷兩個鏈表是否相交。
我們可以采用除留取余法構(gòu)造哈希函數(shù)逞频。
構(gòu)造哈希表可以采用鏈地址法解決沖突纯衍。哈希表沖突指對key1 != key2，存在f(key1)=f(key2)苗胀，鏈地址法就是把key1和key2作為節(jié)點放在同一個單鏈表中托酸，這種表稱為同義詞子表，在哈希表中只存儲同義詞子表的頭指針柒巫，如下圖：
示例代碼就不列舉了励堡，感興趣的可以自己寫寫。
時間復(fù)雜度O(length1 + length2)堡掏。
5.問題轉(zhuǎn)化為判斷一個鏈表是否有環(huán)問題应结。
這個問題我們可以轉(zhuǎn)換為另一個等價問題：如何判斷一個單鏈表是否有環(huán)，若有環(huán)泉唁，找出環(huán)的入口鹅龄？
如何轉(zhuǎn)化？
先遍歷第一個鏈表到它的尾部亭畜，然后將尾部的next指針指向第二個鏈表(尾部指針的next本來指向的是null)扮休。這樣兩個鏈表就合成了一個鏈表。若該鏈表有環(huán)拴鸵，則原兩個鏈表一定相交玷坠。否則蜗搔，不相交。
這樣進行轉(zhuǎn)換后就可以從鏈表頭部進行判斷了八堡，其實并不用樟凄。通過簡單的了解我們就很容易知道，如果新鏈表是有環(huán)的兄渺，那么原來第二個鏈表的頭部一定在環(huán)上缝龄。因此我們就可以從第二個鏈表的頭部進行遍歷的，從而減少了時間復(fù)雜度(減少的時間復(fù)雜度是第一個鏈表的長度)挂谍。
看了下面的示例圖就明白了：
知道了轉(zhuǎn)化的方法后叔壤，那么重點的問題來了。我們?nèi)绾闻袛嘁粋€鏈表是否有環(huán)口叙，如何找到環(huán)的入口百新？
判斷是否有環(huán)，我們一般容易想到的方法就是記錄每個節(jié)點是否被訪問過庐扫，若一個節(jié)點被訪問了兩次饭望，則該鏈表一定有環(huán)。
其實來有一個更為巧妙的方法形庭！
(1)判斷鏈表是否存在環(huán)
設(shè)置兩個鏈表指針fast, slow铅辞，初始值都指向鏈表頭結(jié)點，然后兩個指針都往后走萨醒，不同的是slow每次前進一步斟珊，即前進一個節(jié)點。fast每次前進兩步富纸，如果存在環(huán)囤踩，兩個指針必定相遇。
因為只有存在環(huán)的情況晓褪，我們才可能出現(xiàn)走的快的指針能再次遇到慢的指針堵漱。
并且還有一點就是，若該鏈表存在環(huán)涣仿，則在慢指針還沒走完一整個環(huán)的路程之前勤庐，兩指針已經(jīng)相遇。
為什么好港？因為從慢指針進入環(huán)入口開始計時愉镰，慢指針走完一圈的時間，此時快指針已經(jīng)走了兩圈钧汹。所以在慢指針走完一圈之前丈探，兩指針一定會相遇。
(2)若鏈表有環(huán)拔莱，找到環(huán)的入口點
由(1)我們可以知道碗降，當fast與slow相遇時隘竭，slow還沒走完鏈表，而fast已經(jīng)在環(huán)內(nèi)循環(huán)了n圈了遗锣。
如圖：
我們把兩指針相遇點記為O。則慢指針已走的環(huán)路程記為x嗤形，環(huán)剩下的路程記為y精偿。
設(shè)slow在相遇前走了s步，則fast走了2s步赋兵，設(shè)環(huán)長為r笔咽，有2s=s+nr，即s=nr霹期。
由上圖可知a+x=s, x+y=r叶组，而我們的目標是找到a的位置。a+x=s=nr=(n-1)r+r=(n-1)r+y+x历造，則a=(n-1)r+y. 這個公式告訴我們甩十，從鏈表頭和相遇點O分別設(shè)一個指針，每次各走一步吭产，這兩個指針必定相遇侣监，且相遇的第一個點為環(huán)入口點。
示例代碼如下：
struct Link
{
int data;
Link *next;
};
// 插入節(jié)點
void insertNode(Link *&head, int data)
{
Link *node = new Link;
node->data = data;
node->next = head;
head = node;
}
// 判斷鏈表是否存在環(huán)
Link* hasCycle(Link* head)
{
Link *fast, *slow;
slow = fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return slow;
}
return NULL;
}
// 確定環(huán)的入口點,pos表示fast與slow相遇的位置
Link* findCycleEntry(Link* head, Link* pos)
{
while (head != pos)
{
head = head->next;
pos = pos->next;
}
return head;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
擴展問題：如何判斷兩個存在環(huán)的單鏈表是否相交?如何找出第一個交點臣淤？
通過方法(1)我們能夠分別找出兩個鏈表的相遇點pos1, pos2橄霉，然后還是使用兩個指針fast和slow，都初始化為pos1邑蒋，且fast每次前進2步姓蜂，slow每次前進1步。若fast指針在遇到slow前医吊，出現(xiàn)fast等于pos2或fast->next等于pos2钱慢，則說明兩個鏈表相交，否則不相交卿堂。
若兩鏈表相交滩字，我們可知pos2肯定是兩個鏈表的一個相交點，將這個點看做兩個鏈表的終止節(jié)點御吞，使用我們上面提到的記錄鏈表長度的解法麦箍，即可找到兩個鏈表相交的第一個節(jié)點。
并且需要提示一點的是陶珠，如果兩個帶有環(huán)的鏈表相交挟裂，則這兩個鏈表的環(huán)肯定是同一個環(huán)。
想不通的話可以在紙上畫畫揍诽，你會發(fā)現(xiàn)若相交诀蓉，只會出現(xiàn)這一種情況栗竖。
代碼示例：
// 判斷鏈表是否存在環(huán)
Link* hasCycle(Link* head)
{
Link *fast, *slow;
slow = fast = head;
while (fast && fast->next)
{
fast = fast->next->next;
slow = slow->next;
if (fast == slow)
return slow;
}
return NULL;
}
Link* findFirstCross(Link* head1, Link* head2)
{
Link* pos1 = hasCycle(head1);
Link* pos2 = hasCycle(head2);
// 兩個鏈表都有環(huán)
if (pos1 && pos2)
{
// 判斷這兩個環(huán)是不是同一個環(huán)
Link *tmp = pos1;
do
{
if (pos1 == pos2 ||pos1->next == pos2)
break;
pos1 = pos1->next->next;
tmp = tmp->next;
}while (pos1!=tmp);
// 兩個鏈表的環(huán)不是同一個環(huán),所以沒有交點
if (pos1 != pos2 && pos1->next != pos2)
return NULL;
// 兩個鏈表有共同的交點pos1,現(xiàn)在求第一個交點
int len1, len2;
len1 = len2 = 0;
Link *nd1, *nd2;
nd1 = head1;
while (nd1 != pos1) {len1++;nd1=nd1->next;}
nd2 = head2;
while (nd2 != pos1) {len2++;nd2=nd2->next;}
// 較長鏈表的鏈表的nd先走dif步
int dif;
nd1 = head1; nd2 = head2;
if (len1 >= len2)
{
dif = len1 - len2;
while (dif--) nd1 = nd1->next;
}
else
{
dif = len2 - len1;
while (dif--) nd2 = nd2->next;
}
// 之后兩個nd再一起走,直到nd相等(即為第一個交點)
while (nd1!=pos1 && nd2!=pos1)
{
if (nd1 == nd2)
return nd1;
nd1 = nd1->next;
nd2 = nd2->next;
}
return pos1;
}
}
