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

1、題目：兩個(gè)單向鏈表，找出它們的第一個(gè)公共結(jié)點(diǎn)。鏈表的結(jié)點(diǎn)定義為：structListNodeintm_nKeyListNodem_pNext分析：如果兩個(gè)單向鏈表有公共的結(jié)點(diǎn)，也就是說兩個(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ù)湫螤羁雌饋硐褚粋€(gè)Y，而不

2、可能像X?？吹竭@個(gè)題目，第一反應(yīng)就是蠻力法：在第一鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。每遍歷一個(gè)結(jié)點(diǎn)的時(shí)候，在第二個(gè)鏈表上順序遍歷每個(gè)結(jié)點(diǎn)。如果此時(shí)兩個(gè)鏈表上的結(jié)點(diǎn)是一樣的，說明此時(shí)兩個(gè)鏈表重合，于是找到了它們的公共結(jié)點(diǎn)。如果第一個(gè)鏈表的長度為m，第二個(gè)鏈表的長度為n，顯然，該方法的時(shí)間復(fù)雜度為O(mn)。接下來我們試著去尋找一個(gè)線性時(shí)間復(fù)雜度的算法。我們先把問題簡化：如何判斷兩個(gè)單向鏈表有沒有公共結(jié)點(diǎn)？前面已經(jīng)提到，如果兩個(gè)鏈表有一個(gè)公共結(jié)點(diǎn)，那

3、么該公共結(jié)點(diǎn)之后的所有結(jié)點(diǎn)都是重合的。那么，它們的最后一個(gè)結(jié)點(diǎn)必然是重合的。因此，我們判斷兩個(gè)鏈表是不是有重合的部分，只要分別遍歷兩個(gè)鏈表到最后一個(gè)結(jié)點(diǎn)。如果兩個(gè)尾結(jié)點(diǎn)是一樣的，說明它們用重合；否則兩個(gè)鏈表沒有公共的結(jié)點(diǎn)。在上面的思路中，順序遍歷兩個(gè)鏈表到尾結(jié)點(diǎn)的時(shí)候，我們不能保證在兩個(gè)鏈表上同時(shí)到達(dá)尾結(jié)點(diǎn)。這是因?yàn)閮蓚€(gè)鏈表不一定長度一樣。但如果假設(shè)一個(gè)鏈表比另一個(gè)長l個(gè)結(jié)點(diǎn)，我們先在長的鏈表上遍歷l個(gè)結(jié)點(diǎn)，之后再同步遍歷，這個(gè)時(shí)候我們

4、就能保證同時(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)。templateListNodeFindFirstCommonNode(ListNodepHead1ListNodepHead2)intnLength1=GetListLength(pHead1)intnLength2=GetListLength(