### 這道題分兩種情況討論：鏈表是否存在環（詢問面試官）。 --- #### 無環 思路：如果這兩個鏈表相交，那么從它們的第一個相交的點開始，之后兩個鏈表上的節點都是相同的。因此，我們只要遍歷兩個鏈表判斷最后那個節點是否相同就可以了。 ``` 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中，在的話，則表示兩條鏈表共享環，否則不共享。