### 這道題分兩種情況討論:鏈表是否存在環(詢問面試官)。一些額外的說明:兩個鏈表,第一個是鏈表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也在這個環中,那么這兩個鏈表就是相交的。(這里相當提供了一種方法遍歷環)