求連結清單的第一個公共節點問題（好未來筆試題）

問題描述：給定兩個連結清單的頭指針，判斷兩個連結清單是否存在公共節點，如果存在公共節點，則找出第一個公共節點。

分析：這曾經是我參加好未來的一道筆試題目，給大家分享下解法。

        解法一：蠻力法。拿第一個連結清單的每個節點去和第二個連結清單的每個節點進行比較，如果都不相同，則判斷出兩個連結清單不相交。

                    否則輸出第一個相同的節點。算法的時間複雜度為O(m*n).

        解法二：輔助空間法。仔細觀察可以發現，如果兩個連結清單想要相交，則尾節點必是相交點，否則不相交。

                    是以我們可以從兩個連結清單的尾部開始進行比較，如果不相同，直接判斷出不相交。

                   如果相同，記下這個節點，然後繼續往前比較，如果仍然相同，記下這個節點，如此進行下去，直到碰到不同的節點為止，

                   那上次儲存的節點就是第一個相交的節點。但是由于單連結清單隻能從頭開始周遊，不能從尾部向頭周遊，需要采用一些辦法來實作，

                   這個屬于典型的先進後出，是以可以使用棧來實作，需要利用兩個輔助棧實作，首先将兩個連結清單中的所有節點入棧，然後再從棧頂開始                    比較。

                   算法的時間複雜度為O(m+n).

        解法三:  由于解法二需要額外的輔助空間，可以再加以改進。

                   可以先将兩個連結清單掃描一遍求出各自的長度為m和n，并假設m>=n，這樣，可以先在長的連結清單上周遊m-n個節點，然後再在兩個連結清單                    上同時開始周遊， 并比較節點是否相同，如碰到第一相同的節點，就可以結束了，如果周遊完都沒有相同的節點，那麼就可以判斷                        出，兩個連結清單沒有交點。

                   算法的時間複雜度為O(m).

由于比較簡單，我就不再些具體的代碼了，讀者可以自行驗證。