題目

思路

1.哈希集合

因?yàn)橐笫欠翊嬖谙嘟还?jié)點(diǎn)，那么我們就可以利用哈希集合先將listA鏈表里面的所有數(shù)據(jù)存入，然后訪問(wèn)listB，判斷其是否有節(jié)點(diǎn)在哈希集合中，若存在，則說(shuō)明此節(jié)點(diǎn)為相交的節(jié)點(diǎn)。若遍歷完之后仍沒(méi)有發(fā)現(xiàn)，則說(shuō)明兩個(gè)表之間不存在相交節(jié)點(diǎn)，返回nullptr即可。

2.雙指針

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

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

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

假設(shè)鏈表?headA?的長(zhǎng)度為?m，鏈表?headB?的長(zhǎng)度為?n，且它們的交點(diǎn)之后的公共部分長(zhǎng)度為?k。

• 當(dāng)?cur1?遍歷完?headA?后，它會(huì)開(kāi)始遍歷?headB，此時(shí)?cur1?已經(jīng)走了?m?步。

• 當(dāng)?cur2?遍歷完?headB?后，它會(huì)開(kāi)始遍歷?headA，此時(shí)?cur2?已經(jīng)走了?n?步。

• 當(dāng)?cur1?和?cur2?都開(kāi)始遍歷對(duì)方的鏈表時(shí)，它們會(huì)在交點(diǎn)處相遇，因?yàn)榇藭r(shí)?cur1?和?cur2?都走了?m + n - k?步。

如果兩個(gè)鏈表沒(méi)有交點(diǎn)，那么?cur1?和?cur2?最終都會(huì)指向?nullptr，此時(shí)返回?nullptr。

下面舉個(gè)例子來(lái)看就容易理解了

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

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

• 鏈表 listA?的長(zhǎng)度為?m = 6。

• 鏈表 listB?的長(zhǎng)度為?n = 5。

• 交點(diǎn)之后的公共部分長(zhǎng)度為?k = 3（即?C1 -> C2 -> C3）。

運(yùn)行過(guò)程：

1. 初始化指針：

   • cur1?指向?A1。

   • cur2?指向?B1。

2. 遍歷過(guò)程：

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

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

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

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

3. 相遇點(diǎn)：

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

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

   • 兩者會(huì)在交點(diǎn)?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;}
};