題目

思路

1.哈希集合

因為要求是否存在相交節(jié)點，那么我們就可以利用哈希集合先將listA鏈表里面的所有數(shù)據存入，然后訪問listB，判斷其是否有節(jié)點在哈希集合中，若存在，則說明此節(jié)點為相交的節(jié)點。若遍歷完之后仍沒有發(fā)現(xiàn)，則說明兩個表之間不存在相交節(jié)點，返回nullptr即可。

2.雙指針

首先進行條件判斷，若headA和headB中有一個為空，則說明不可能有相交節(jié)點，直接返回nullptr即可。

接著用cur1和cur2變量用來遍歷listA和listB鏈表，循環(huán)中用了三元運算符，就第一個來說，若cur1為空，則直接將cur1賦值為headB,若不為空，則繼續(xù)往下移動。

第二個也是如此，那為什么這樣就可以求出它們的相交節(jié)點呢？

假設鏈表?headA?的長度為?m，鏈表?headB?的長度為?n，且它們的交點之后的公共部分長度為?k。

• 當?cur1?遍歷完?headA?后，它會開始遍歷?headB，此時?cur1?已經走了?m?步。

• 當?cur2?遍歷完?headB?后，它會開始遍歷?headA，此時?cur2?已經走了?n?步。

• 當?cur1?和?cur2?都開始遍歷對方的鏈表時，它們會在交點處相遇，因為此時?cur1?和?cur2?都走了?m + n - k?步。

如果兩個鏈表沒有交點，那么?cur1?和?cur2?最終都會指向?nullptr，此時返回?nullptr。

下面舉個例子來看就容易理解了

listA: A1 -> A2 -> A3 -> C1 -> C2 -> C3

listB: B1 -> B2 -> C1 -> C2 -> C3

• 鏈表 listA?的長度為?m = 6。

• 鏈表 listB?的長度為?n = 5。

• 交點之后的公共部分長度為?k = 3（即?C1 -> C2 -> C3）。

運行過程：

1. 初始化指針：

   • cur1?指向?A1。

   • cur2?指向?B1。

2. 遍歷過程：

   • cur1?依次遍歷：A1 -> A2 -> A3 -> C1 -> C2 -> C3 -> nullptr。

   • 當?cur1?到達?nullptr?時，它已經走了?m = 6?步，然后切換到?listB，繼續(xù)遍歷：B1 -> B2 -> C1。

   • cur2?依次遍歷：B1 -> B2 -> C1 -> C2 -> C3 -> nullptr。

   • 當?cur2?到達?nullptr?時，它已經走了?n = 5?步，然后切換到?listA?，繼續(xù)遍歷：A1 -> A2 -> A3 -> C1。

3. 相遇點：

   • 當?cur1?切換到?listB?后，它走了?m + n - k = 6 + 5 - 3 = 8?步。

   • 當?cur2?切換到?listA??后，它走了?n + m - k = 5 + 6 - 3 = 8?步。

   • 兩者會在交點?C1?處相遇。

代碼

1.哈希集合

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {unordered_set<ListNode*> s;while(headA){s.insert(headA);headA = headA->next;}while(headB){if(s.count(headB)){return headB;}headB = headB->next;}return nullptr;}
};

2.雙指針

class Solution {
public:ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {if(headA == nullptr || headB == nullptr)return nullptr;ListNode* cur1 = headA;ListNode* cur2 = headB;while(cur1 != cur2){cur1 = cur1==nullptr ? headB : cur1->next;cur2 = cur2==nullptr ? headA : cur2->next;}return cur1;}
};