### 這道題分兩種情況討論：鏈表是否存在環（詢問面試官）。一些額外的說明：兩個鏈表，第一個是鏈表A，長度為m，第二個是鏈表B，長度為n。 --- #### 無環 **第一種方法**：樸素的方法是將以鏈表A的每一個節點為key，對著鏈表B做一次遍歷，直到找到第一個公共節點，或者沒有公共節點，直接返回nullptr。時間復雜度為O(mn)，空間復雜度為O(1)。這種方法的一種直接改進是使用哈希表保存鏈表A的每一個節點，因為之前的方法主要是查找消耗時間，這樣做是以空間換時間（哈希表需要O(m)的空間保存），時間復雜度為O(m + n)。 **第二種方法**：不使用額外空間，但是時間也是O(m + n)。先遍歷兩個鏈表（因為沒有環，所以直接遍歷就可以），求出它們的長度 m 和 n。然后長的鏈表先走 | m - n | 步，之后再同時向前走，直到找到第一個公共節點。 下面實現第二種方法： ``` // 返回值：有公共節點，則返回第一個，否則，返回nullptr SList* findFirstCommonNode(SList *list1, SList *list2) { unsigned int lengthOfList1 = getListLength(list1); unsigned int lengthOfList2 = getListLength(list2); SList *longList = list1, *shortList = list2; unsigned int deltaOfLength = lengthOfList1 - lengthOfList2; if (lengthOfList1 < lengthOfList2) { longList = list2; shortList = list1; deltaOfLength = lengthOfList2 - lengthOfList1; } // 長鏈表先走 deltaOfLength 步 for (unsigned int i = 0; i < deltaOfLength; ++i) { longList = longList->m_next; } while ( (longList != nullptr) && (shortList != nullptr) && (longList != shortList)) { longList = longList->m_next; shortList = shortList->m_next; } return longList; } // 求鏈表長度 unsigned int getListLength(SList *list) { unsigned int length = 0; while (list != nullptr) { ++length; list = list->m_next; } return length; } ``` #### 不知道是否有環 這種情況我們需要先[判斷鏈表是否有環](http://www.hmoore.net/persuez/algorithm/858057)。 1. 兩個鏈表都沒有環， 按上面無環的算法走； 2. 一個有環，一個無環，這兩個鏈表不可能相交，返回nullptr； 3. 兩個都有環，此時兩條鏈表如果相交，那么一定共享這個環。但如果相交的話，我們取哪個作為第一個公共節點呢？有人取下面的公共節點pos2作為兩個鏈表的最后一個節點，然后用無環的方法求第一個公共節點，但我覺得似乎也沒有什么特別意義。所以我們的主要任務就判斷這個環是不是共有的就好了。我們在判斷是否有環時返回兩個鏈表的相遇點，記為pos1，pos2。然后我們在pos1點設置快慢指針，慢指針每次走一步，快指針每次走兩步，那么在它們再次相遇時慢指針（或者快指針和快指針的m_next）一定遍歷了整個環，而這個環是共享的，所以如果pos2也在這個環中，那么這兩個鏈表就是相交的。（這里相當提供了一種方法遍歷環）