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)開始，它們的m_pNext都指向同一個(gè)結(jié)點(diǎn)。但由于是單向鏈表的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)只有一個(gè)m_pNext，因此從第一個(gè)公共結(jié)點(diǎn)開始，之后它們所有結(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)。如果此時(shí)兩個(gè)鏈表

2、上的結(jié)點(diǎn)是一樣的，說(shuō)明此時(shí)兩個(gè)鏈表重合，于是找到了它們的公共結(jié)點(diǎn)。如果第一個(gè)鏈表的長(zhǎng)度為m，第二個(gè)鏈表的長(zhǎng)度為n，顯然，該方法的時(shí)間復(fù)雜度為O(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í)候，我們不能保證在兩個(gè)鏈表上同時(shí)

3、到達(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ù)雜度為O(m+n)。代碼：temp

4、late<typename T> struct ListNode T 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<T>

5、;* 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 && pHead1 !=