35.兩連結清單的第一個公共結點

題目：兩個單向連結清單，找出它們的第一個公共結點。

連結清單的結點定義為：

分析：這是一道微軟的面試題。微軟非常喜歡與連結清單相關的題目，是以在微軟的面試題中，連結清單出現的機率相當高。

如果兩個單向連結清單有公共的結點，也就是說兩個連結清單從某一結點開始，它們的m_pNext都指向同一個結點。但由于是單向連結清單的結點，每個結點隻有一個m_pNext，是以從第一個公共結點開始，之後它們所有結點都是重合的，不可能再出現分叉。是以，兩個有公共結點而部分重合的連結清單，拓撲形狀看起來像一個Y，而不可能像X。

看到這個題目，第一反應就是蠻力法：在第一連結清單上順序周遊每個結點。每周遊一個結點的時候，在第二個連結清單上順序周遊每個結點。如果此時兩個連結清單上的結點是一樣的，說明此時兩個連結清單重合，于是找到了它們的公共結點。如果第一個連結清單的長度為m，第二個連結清單的長度為n，顯然，該方法的時間複雜度為O(mn)。

接下來我們試着去尋找一個線性時間複雜度的算法。我們先把問題簡化：如何判斷兩個單向連結清單有沒有公共結點？前面已經提到，如果兩個連結清單有一個公共結點，那麼該公共結點之後的所有結點都是重合的。那麼，它們的最後一個結點必然是重合的。是以，我們判斷兩個連結清單是不是有重合的部分，隻要分别周遊兩個連結清單到最後一個結點。如果兩個尾結點是一樣的，說明它們用重合；否則兩個連結清單沒有公共的結點。

在上面的思路中，順序周遊兩個連結清單到尾結點的時候，我們不能保證在兩個連結清單上同時到達尾結點。這是因為兩個連結清單不一定長度一樣。但如果假設一個連結清單比另一個長l個結點，我們先在長的連結清單上周遊l個結點，之後再同步周遊，這個時候我們就能保證同時到達最後一個結點了。由于兩個連結清單從第一個公共結點開始到連結清單的尾結點，這一部分是重合的。是以，它們肯定也是同時到達第一公共結點的。于是在周遊中，第一個相同的結點就是第一個公共的結點。

在這個思路中，我們先要分别周遊兩個連結清單得到它們的長度，并求出兩個長度之差。在長的連結清單上先周遊若幹次之後，再同步周遊兩個連結清單，知道找到相同的結點，或者一直到連結清單結束。此時，如果第一個連結清單的長度為m，第二個連結清單的長度為n，該方法的時間複雜度為O(m+n)。

基于這個思路，我們不難寫出如下的代碼：