兩個(gè)單向鏈表,找出它們的第一個(gè)公共結(jié)點(diǎn)只是分享

1、題目：兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。鏈表的結(jié)點(diǎn)定義為：struct ListNodeint m_nKey;ListNode* m_pNext;分析：如果兩個(gè)單向鏈表有公共的結(jié)點(diǎn)，也就是說(shuō)兩個(gè)鏈表從某一結(jié)點(diǎn)開(kāi)始，它們的 m_pNext 都指向同一個(gè)結(jié)點(diǎn)。但由于是單向鏈表的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只有一個(gè) m_pNext ，因此從第一個(gè)公 共結(jié)點(diǎn)開(kāi)始，之后它們所有結(jié)點(diǎn)都是重合的，不可能再出現(xiàn)分叉。所以，兩個(gè)有公共結(jié)點(diǎn)而部 分重合的鏈表，拓?fù)湫螤羁雌饋?lái)像一個(gè)Y ，而不可能像 X?？吹竭@個(gè)題目，第一反應(yīng)就是蠻力法：在第一鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。每遍歷一個(gè)結(jié)點(diǎn)的時(shí) 候，在第二個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。如

2、果此時(shí)兩個(gè)鏈表上的結(jié)點(diǎn)是一樣的，說(shuō)明此時(shí)兩個(gè) 鏈表重合，于是找到了它們的公共結(jié)點(diǎn)。如果第一個(gè)鏈表的長(zhǎng)度為m,第二個(gè)鏈表的長(zhǎng)度為n,顯然，該方法的時(shí)間復(fù)雜度為 0(mn)。接 下來(lái)我們?cè)囍ふ乙粋€(gè)線性時(shí)間復(fù)雜度的算法。我們先把問(wèn)題簡(jiǎn)化：如何判斷兩個(gè)單向 鏈表有沒(méi)有公共結(jié)點(diǎn)？前面已經(jīng)提到,如果兩個(gè)鏈表有一個(gè)公共結(jié)點(diǎn),那么該公共結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都是重合的。那么,它們的最后一個(gè)結(jié)點(diǎn)必然是重合的。因此,我們判斷兩個(gè)鏈表 是不是有重合的部分,只要分別遍歷兩個(gè)鏈表到最后一個(gè)結(jié)點(diǎn)。如果兩個(gè)尾結(jié)點(diǎn)是一樣的,說(shuō)明它們用重合；否則兩個(gè)鏈表沒(méi)有公共的結(jié)點(diǎn)。在上面的思路中,順序遍歷兩個(gè)鏈表到尾結(jié)點(diǎn)的時(shí)候,我們不能保

3、證在兩個(gè)鏈表上同時(shí)到達(dá)尾 結(jié)點(diǎn)。這是因?yàn)閮蓚€(gè)鏈表不一定長(zhǎng)度一樣。但如果假設(shè)一個(gè)鏈表比另一個(gè)長(zhǎng)l 個(gè)結(jié)點(diǎn),我們先在長(zhǎng)的鏈表上遍歷 l 個(gè)結(jié)點(diǎn),之后再同步遍歷,這個(gè)時(shí)候我們就能保證同時(shí)到達(dá)最后一個(gè)結(jié)點(diǎn) 了。由于兩個(gè)鏈表從第一個(gè)公共結(jié)點(diǎn)考試到鏈表的尾結(jié)點(diǎn),這一部分是重合的。因此,它們肯 定也是同時(shí)到達(dá)第一公共結(jié)點(diǎn)的。于是在遍歷中,第一個(gè)相同的結(jié)點(diǎn)就是第一個(gè)公共的結(jié)點(diǎn)。在這個(gè)思路中,我們先要分別遍歷兩個(gè)鏈表得到它們的長(zhǎng)度,并求出兩個(gè)長(zhǎng)度之差。在長(zhǎng)的鏈 表上先遍歷若干次之后,再同步遍歷兩個(gè)鏈表,知道找到相同的結(jié)點(diǎn),或者一直到鏈表結(jié)束。此時(shí)，如果第一個(gè)鏈表的長(zhǎng)度為m,第二個(gè)鏈表的長(zhǎng)度為n,該方法的時(shí)間復(fù)雜

4、度為O(m+n) 。代碼：template<typename T>struct ListNodeT data;ListNode* pNext;template<typename T> int GetListLength(ListNode<T>* pHead)int nLength = 0;while(pHead)+nLength;pHead = pHead->pNext;return nLength;template<typename T>ListNode<T>* FindFirstCommonNode(ListNode<

5、T>* pHead1, ListNode<T>* pHead2) int nLength1 = GetListLength(pHead1);int nLength2 = GetListLength(pHead2);/ 交換兩鏈表，是 1為較長(zhǎng)的鏈表if(nLength1 < nLength2)ListNode<T>* pTemp = pHead1;pHead1 = pHead2;pHead2 = pTemp;for(int i = 0; i < nLength1 - nLength2; +i)pHead1 = pHead1->pNext;while(pHead1 && pHe