題目描述

輸入兩個鏈表，找出它們的第一個公共節(jié)點，如圖兩個鏈表從C1開始相交

1、哈希與集合

實現(xiàn)思路：將第一個鏈表的所有節(jié)點存入集合中，遍歷第二個鏈表，并在集合中查詢鏈表二的節(jié)點是否出現(xiàn)過

實現(xiàn)代碼：

struct ListNode* getInteractionNode_hash(struct ListNode* headA, struct ListNode* headB)
{
    set<ListNode*> st;
    while (headA != NULL) {
        st.insert(headA);
        headA = headA->next;
    }
    while (headB != NULL) {
        if (st.count(headB) !=  0)return headB;
        headB = headB->next;
    }
    return NULL;
}

?

2、使用棧

實現(xiàn)思路：根據(jù)題意可知在相同節(jié)點之后，兩鏈表的節(jié)點完全相同，這里我們可以利用棧結構后進先出的特點來實現(xiàn)這一題，分別將兩鏈表存儲棧內(nèi)，同時取出棧頂元素進行對比，當遇到不同節(jié)點之后返回上一節(jié)點（prev）

實現(xiàn)代碼：

struct ListNode* getInteractionNode_stack(struct ListNode* headA, struct ListNode* headB)
{
    stack<ListNode*>stkA, stkB;
    while (headA != NULL) {
        stkA.push(headA);
        headA = headA->next;
    }
    while (headB != NULL) {
        stkB.push(headB);
        headB = headB->next;
    }
    ListNode* prevA = NULL, *prevB = NULL;
    while (stkA.size() != 0 && stkB.size() != 0) {
        ListNode* currA = stkA.top();
        stkA.pop();
        ListNode* currB = stkB.top();
        stkB.pop();
        if (currA != currB)break;
        prevA = currA;
        prevB = currB;
    }
    return prevA;
}

3、補差法

實現(xiàn)思路：在兩鏈表大小相同時，我們完全可以使用循環(huán)的方式逐個判斷兩鏈表節(jié)點是否相同。所以，遵循這一思路衍生出了兩種方法：補差法和拼接法。這里我們先介紹補差法，補差法顧名思義，將兩個不同長度的鏈表的長度差補上。這里的補指的是在循環(huán)判斷節(jié)點相同之前提前移動較長鏈表的節(jié)點，保證后續(xù)對比可以同步進行。因為兩鏈表之前的節(jié)點全部不相同，所以可以很放心的移動節(jié)點。進而完成問題。

實現(xiàn)代碼

struct ListNode* getInteractionNode_sub(struct ListNode* headA, struct ListNode* headB)
{
    if (headA == NULL || headB == NULL)return NULL;
    ListNode *currA = headA, *currB = headB;
    int la = 0, lb = 0;
    while (currA != NULL) {
        ++la;
        currA = currA->next;
    }
    while (currB != NULL) {
        ++lb;
        currB = currB->next;
    }
    int sub = la > lb ? la - lb : lb - la;
    currA = headA;
    currB = headB;
    if (la > lb)
    {
        int cnt = 0;
        while (cnt < sub) {
            ++cnt;
            currA = currA->next;
        }
    }
    if (lb >la) {
        int cnt = 0;
        while (cnt < sub) {
            ++cnt;
            currB = currB->next;
        }
    }
    while (currA != currB) {
        currA = currA->next;
        currB = currB->next;
    }
    return currA;
}

4、雙指針法

實現(xiàn)思路：我們?yōu)榱私鉀Q兩鏈表長度不等的問題，衍生出了雙指針法（拼接法）。在這里我們可以將理解鏈表理解成兩部分，不同部分（Left）和相同部分（Right）。導致兩鏈表長度不相同的部分為Left部分，這里我們可以利用拼接的方式處理這個問題。

?先看下方鏈表：

A ：1 2 3 4 5

B ：7 5 4 5

拼接AB與BA

AB ：1 2 3 4 5 7 5 4 5

BA ：7 5 4 5 1 2 3 4 5

不難發(fā)現(xiàn)AB與BA尾部完全相同，這里的尾部就是兩鏈表相同部分（Right）

如果用公式表達出兩鏈表的內(nèi)容可以得到

AB = Left(A) + Right(A) + Left(B) + Right(B)

BA = Left(B) + Right(B) +?Left(A) + Right(A)

根據(jù)定義理解Right(A）= Right（B）

Left(A) + Right(A) + Left(B) =?Left(B) + Right(B) +?Left(A)恒成立

所以對于長度不同的鏈表可以使用拼接的方法使其總長度相同，進而使其可以比較。

在代碼實現(xiàn)方面，我們并不需要直接將兩鏈表拼接，只需要在鏈表循環(huán)至NULL時再從另一個鏈表開始遍歷即可，這里就完成了進一步優(yōu)化。

代碼實現(xiàn)?

struct ListNode* getInteractionNode_connect(struct ListNode* headA, struct ListNode* headB)
{
    if (headA == NULL || headB == NULL)return NULL;
    ListNode *currA = headA, *currB = headB;
    while (currA != currB) {
        currA = currA->next;
        currB = currB->next;
        //在拼接后遍歷結束時 currA == currB一定成立
        //防止兩鏈表完全不同導致死循環(huán) 給予null出口 
        if (currA != currB) {
            //兩鏈表長度不同 第一次遍歷結束時候
            if (currA == NULL) {
                currA = headB;
            }
            if (currB == NULL) {
                currB = headA;
            }
        }
    }
    return currA;
}

你變成我，走過我走過的路。
我變成你，走過你走過的路。
然后我們便相遇了..??

——leetcode

希望對大家能有所幫助。

圖片來源：編程導航算法通關村第一期

具體來源：算法通關村第一關——鏈表—白銀挑戰(zhàn)

作者：余秋文章來源地址http://www.zghlxwxcb.cn/news/detail-640786.html

到了這里，關于算法學習-鏈表-level2-兩個鏈表的第一個公共節(jié)點的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！