目錄

• 查找鏈表相交節點
• • 情況1: 無環鏈表相交
  • 情況3：鏈表相交于入環前及入環節點
  • 情況4：鏈表A、B相交于入環后或不相交

查找鏈表相交節點

先判斷鏈表A和B是否有環，并分別找到他們的環入口(loopA,loopB)，具體方法可以參考我的上一篇博客判斷鏈表中是否有環，并查找鏈表環入口。

可能有以下幾種情況：

1. (loopA == NULL && loopB == NULL)；鏈表A、B均無環；2. ((!loopA && loopB) || (loopA && !loopB))；鏈表A、B中有一個有環，有一個無環，這種情況A、B必定不相交；3. (loopA == loopB && loopA)；鏈表A、B相交于入環前或入環節點4. (loopA != loopB && loopA && loopB)；鏈表A、B相交于入環后（不包括入環節點），或不相交

情況1: 無環鏈表相交

指針pA指向鏈表A頭節點(A1)，pB指向鏈表B節點(B1)，pA，pB均每次前進一步。當pA到達鏈表A尾部，令pA指向B1;同樣，pB到達鏈表B尾部，令pB指向A1。當pA等于pB時，即為A，B相交節點。

pA經過的節點為: A1->A2->C1->C2->B1->B2->B3->C1pB經過的節點為: B1->B2->B3->C1->C2->A1->A2->C1

將A，B鏈表中的節點分為3個部分:
1. 鏈表A獨立節點；
2. 鏈表B的獨立節點；
3. 鏈表A、B的共同部分；
由上可知，pA、pB指針在第二次到達鏈表A、B鏈表相交節點時，必定分別遍歷一次鏈表中第1,2,3部分，所以此時pA、pB必定同時到達相交節點（即pA==pB）。

鏈表沒有相交時，可以認為相交于尾節點后一個節點(NULL）。

代碼如下：

// 返回鏈表相交節點，若沒有相交返回NULL // 不考慮鏈表中存在環路的情況 ListNode *getIntersectionNodeNoLoop(ListNode *headA, ListNode *headB) {if(!headA || !headB) return NULL;ListNode *pa = headA;ListNode *pb = headB;while(pa != pb){pa = pa ? pa->next : headB;pb = pb ? pb->next : headA;}return pa; }

情況3：鏈表相交于入環前及入環節點

將入環節點當做鏈表A、B的尾節點，此時，查找相交節點方式與無環鏈表相同。

// 返回鏈表相交節點，若沒有相交返回NULL // 相交節點位于入環前 // loop 為鏈表中環的入口節點，因為相交于入環前，所以兩個鏈表入口節點相同 ListNode *getIntersectionNodeBeforeNode(ListNode *headA, ListNode *headB, ListNode *loop) {if(!headA || !headB) return NULL;ListNode *pa = headA;ListNode *pb = headB;while(pa != pb){pa = pa != loop ? pa->next : headB;pb = pb != loop ? pb->next : headA;}return pa; }

情況4：鏈表A、B相交于入環后或不相交

首先判斷鏈表是否相交，指針cur從鏈表A的入口節點loopA開始每次前進一步，若找到與鏈表B入口節點loopB相同節點，則鏈表A、B相交；若cur再次到達loopA，依然沒有與loopB相同節點，則不相交。

bool IsIntersection(ListNode *loopA, ListNode *loopB){ListNode *cur = loopA;while(cur != loopB){cur == cur->next;if(cur == loopA) return false;}return true; }

在這種情況下，若A、B相交，loopA和loopB均為相交節點。

ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {// 獲取鏈表入環節點,見[判斷鏈表中是否有環，并查找鏈表環入口](https://blog.csdn.net/hander_left/article/details/107718329)ListNode *loopA = detectCycle(headA);ListNode *loopB = detectCycle(headB);if(loopA == NULL && loopB == NULL) { // 情況1：無環鏈表return getIntersectionNodeNoLoop(headA, headB);}if(loopA == NULL || loopB == NULL){ // 情況2：不相交return NULL;}if(loopA == loopB) { // 情況3: 相交于入環前或入環節點return getIntersectionNodeBeforeNode(headA, headB, loopA);} // 情況4if(IsIntersection(loopA, loopB){return loopA; // return loopB;}return NULL; }

總結

以上是生活随笔為你收集整理的查找相交链表相交节点的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。