### 這道題分兩種情況討論:鏈表是否存在環(詢問面試官)。
---
#### 無環
思路:如果這兩個鏈表相交,那么從它們的第一個相交的點開始,之后兩個鏈表上的節點都是相同的。因此,我們只要遍歷兩個鏈表判斷最后那個節點是否相同就可以了。
```
bool isInteractNoLoop(SList *list1, SList *list2)
{
if (list1 == nullptr || list2 == nullptr) {
return false;
}
SList *lastNode1 = list1, *lastNode2 = list2;
// 兩個 while 循環分別求出兩個鏈表的最后一個節點
while (list1 != nullptr) {
lastNode1 = list1;
list1 = list1->m_next;
}
while (list2 != nullptr) {
lastNode2 = list2;
list2 = list2->m_next;
}
return (lastNode1 == lastNode2);
}
```
#### 不知道是否有環
這種情況我們需要先[判斷鏈表是否有環](http://www.hmoore.net/persuez/algorithm/858057)。
1. 兩個鏈表都沒有環, 按上面無環的算法走;
2. 一個有環,一個無環,這兩個鏈表不可能相交;
3. 兩個都有環,此時兩條鏈表如果相交,那么一定共享這個環。所以我們可以在判斷鏈表A是否有環時返回碰撞點,然后遍歷B鏈表查看碰撞點是否也在B中,在的話,則表示兩條鏈表共享環,否則不共享。