前言

本文章一部分內(nèi)容參考于《代碼隨想錄》----如有侵權(quán)請聯(lián)系作者刪除即可，撰寫本文章主要目的在于記錄自己學(xué)習(xí)體會并分享給大家，全篇并不僅僅是復(fù)制粘貼，更多的是加入了自己的思考，希望讀完此篇文章能真正幫助到您?。?！

面試題（鏈表相交）—（保姆級別講解）

分析題目：

1. 兩個鏈表都是單鏈表
2. 目標是找到并且返回兩個單鏈表的相交的起始節(jié)點（假設(shè)現(xiàn)在有兩個單鏈表分別是A和B，我們先不管A和B這兩個單鏈表的長度誰長誰短，我們需要將A和B的尾節(jié)點對齊）
3. 整個鏈式結(jié)構(gòu)不存在環(huán)

鏈表相交代碼：

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        ListNode* curA = headA;
        ListNode* curB = headB;
        int lenA = 0, lenB = 0;
        while (curA != NULL) { 
            lenA++;
            curA = curA->next;
        }
        while (curB != NULL) { 
            lenB++;
            curB = curB->next;
        }
        curA = headA;
        curB = headB;
       
        if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }
        
        int gap = lenA - lenB;
       
        while (gap--) {
            curA = curA->next;
        }
        
        while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
        return NULL;
    }
};

時間復(fù)雜度：O(n + m)
空間復(fù)雜度：O(1)

算法思想

好！按照老樣子，接下來開始詳細講解每行代碼的用處，以及為什么這樣寫！

ListNode* curA = headA;
ListNode* curB = headB;

//設(shè)置兩個指針curA和curB分別指向鏈表A和鏈表B的頭節(jié)點。

int lenA = 0, lenB = 0;

//設(shè)置鏈表A和鏈表B的長度，并初始化為0

while (curA != NULL) { 
            lenA++;
            curA = curA->next;
        }

while (curB != NULL) { 
            lenB++;
            curB = curB->next;
        }

//計算鏈表A和鏈表B的節(jié)點數(shù)量，也就是計算鏈表長度。

curA = headA;
curB = headB;

//設(shè)置兩個指針curA和curB分別指向鏈表A和鏈表B的頭節(jié)點。

if (lenB > lenA) {
            swap (lenA, lenB);
            swap (curA, curB);
        }

//因為有三種情況，分別是lenB > lenA或者lenB < lenA或者lenB = lenA，當lenB = lenA時自然不需要處理。所以我們?yōu)榱私y(tǒng)一操作標準，不管鏈表A的長度長還是鏈表B的長度長，都設(shè)置為鏈表A的長度比鏈表B的長度長。

int gap = lenA - lenB;

//計算鏈表A和鏈表B的長度差

while (gap--) {
            curA = curA->next;
        }

//該操作讓curA和curB在同一點上，即讓鏈表A和鏈表B的末尾位置對齊

while (curA != NULL) {
            if (curA == curB) {
                return curA;
            }
            curA = curA->next;
            curB = curB->next;
        }
return NULL;

//遍歷鏈表A和鏈表B（分別從curA和curB開始），如果發(fā)現(xiàn)相同，則代表成功找到交點。如果不相同，則同時向后移動curA和curB。否則循環(huán)退出返回空指針

結(jié)束語

如果覺得這篇文章還不錯的話，記得點贊 ，支持下！??！文章來源地址http://www.zghlxwxcb.cn/news/detail-443740.html

到了這里，關(guān)于看完這篇文章你就徹底懂啦｛保姆級講解｝-----（面試刷題鏈表相交） 2023.4.24的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！