目錄

160.相交鏈表

?題目

思路

代碼?

141.環(huán)形鏈表

?題目

思路

代碼

142.環(huán)形鏈表II

題目

思路

代碼

160.相交鏈表

160. 相交鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/intersection-of-two-linked-lists/description/

?題目

給你兩個(gè)單鏈表的頭節(jié)點(diǎn)?headA?和?headB?，請(qǐng)你找出并返回兩個(gè)單鏈表相交的起始節(jié)點(diǎn)。如果兩個(gè)鏈表不存在相交節(jié)點(diǎn)，返回?null?。

圖示兩個(gè)鏈表在節(jié)點(diǎn)?c1?開(kāi)始相交：

題目數(shù)據(jù)?保證?整個(gè)鏈?zhǔn)浇Y(jié)構(gòu)中不存在環(huán)。

注意，函數(shù)返回結(jié)果后，鏈表必須?保持其原始結(jié)構(gòu)?。

示例：

輸入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,6,1,8,4,5], skipA = 2, skipB = 3
輸出：Intersected at '8'
解釋：相交節(jié)點(diǎn)的值為 8 （注意，如果兩個(gè)鏈表相交則不能為 0）。
從各自的表頭開(kāi)始算起，鏈表 A 為 [4,1,8,4,5]，鏈表 B 為 [5,6,1,8,4,5]。
在 A 中，相交節(jié)點(diǎn)前有 2 個(gè)節(jié)點(diǎn)；在 B 中，相交節(jié)點(diǎn)前有 3 個(gè)節(jié)點(diǎn)。
— 請(qǐng)注意相交節(jié)點(diǎn)的值不為 1，因?yàn)樵阪湵?A 和鏈表 B 之中值為 1 的節(jié)點(diǎn) (A 中第二個(gè)節(jié)點(diǎn)和 B 中第三個(gè)節(jié)點(diǎn)) 是不同的節(jié)點(diǎn)。換句話說(shuō)，它們?cè)趦?nèi)存中指向兩個(gè)不同的位置，而鏈表 A 和鏈表 B 中值為 8 的節(jié)點(diǎn) (A 中第三個(gè)節(jié)點(diǎn)，B 中第四個(gè)節(jié)點(diǎn)) 在內(nèi)存中指向相同的位置。

思路

?先分別從兩個(gè)單鏈表A、B的頭節(jié)點(diǎn)開(kāi)始遍歷，分別計(jì)算出兩個(gè)單鏈表的長(zhǎng)度lenA、lenB，由于相交節(jié)點(diǎn)后面部分鏈表是共用的，所以長(zhǎng)度差只存在于相交節(jié)點(diǎn)前面部分，因此，我們可以讓較長(zhǎng)的鏈表（可以先假設(shè)A長(zhǎng)）先往后遍歷差距步abs(lenA-lenB),再讓A、B鏈表同時(shí)向后遍歷(longlistA=longlistA->next、shortlistB=shortlistB->next)，當(dāng)A、B遍歷到相同的節(jié)點(diǎn)時(shí)，即longlistA==shortlistB時(shí)，同時(shí)到達(dá)相交起始節(jié)點(diǎn)，返回longlist或者shortlist均為相交起始節(jié)點(diǎn)。

圖示??

代碼?

struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)
    return NULL;

int grp=0;
if(lenA>lenB)
grp=lenA-lenB;
else
grp=lenB-lenA;

struct ListNode* longlist=headA,* shortlist = headB;

if(lenA<lenB)
{
    longlist=headB;
    shortlist=headA;
}
//長(zhǎng)的先走差距步
while(grp--)
{
    longlist=longlist->next;
}
while(longlist!=shortlist)
{
    longlist=longlist->next;
    shortlist=shortlist->next;
}
return longlist;

}

141.環(huán)形鏈表

141. 環(huán)形鏈表 - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle/description/

?題目

給你一個(gè)鏈表的頭節(jié)點(diǎn)?head?，判斷鏈表中是否有環(huán)。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù)?pos?來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。注意：pos?不作為參數(shù)進(jìn)行傳遞?。僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

如果鏈表中存在環(huán)?，則返回?true?。 否則，返回?false?。

示例：

輸入：head = [3,2,0,-4], pos = 1
輸出：true
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

思路

利用快慢指針?lè)ǎ陬^節(jié)點(diǎn)創(chuàng)建兩個(gè)指針fast和slow，從頭節(jié)點(diǎn)向后分別開(kāi)始遍歷，但是fast一次走兩步(fast=fast->next->next)，slow一次走一步(slow=slow->next)，如果鏈表中有環(huán)，沒(méi)有指向NULL的節(jié)點(diǎn)，fast和slow進(jìn)入環(huán)后會(huì)無(wú)限循環(huán)遍歷下去，因?yàn)閒ast遍歷速度是slow的兩倍，在環(huán)中，fast和slow總會(huì)遍歷到同一節(jié)點(diǎn)，我們就可以添加一個(gè)跳出條件，當(dāng)fast和slow相等時(shí)(fast==slow)，證明鏈表中有環(huán)，返回true。

圖示??

代碼

bool hasCycle(struct ListNode *head) {
    struct ListNode* slow=head,* fast=head;

    while(fast&&fast->next)
    {
        slow=slow->next;
        fast=fast->next->next;

        if(fast==slow)
        return true;
    }
    return false;
}

142.環(huán)形鏈表II

?142. 環(huán)形鏈表 II - 力扣（LeetCode）https://leetcode.cn/problems/linked-list-cycle-ii/description/

題目

給定一個(gè)鏈表的頭節(jié)點(diǎn) ?head?，返回鏈表開(kāi)始入環(huán)的第一個(gè)節(jié)點(diǎn)。?如果鏈表無(wú)環(huán)，則返回?null。

如果鏈表中有某個(gè)節(jié)點(diǎn)，可以通過(guò)連續(xù)跟蹤?next?指針再次到達(dá)，則鏈表中存在環(huán)。 為了表示給定鏈表中的環(huán)，評(píng)測(cè)系統(tǒng)內(nèi)部使用整數(shù)?pos?來(lái)表示鏈表尾連接到鏈表中的位置（索引從 0 開(kāi)始）。如果?pos?是?-1，則在該鏈表中沒(méi)有環(huán)。注意：pos?不作為參數(shù)進(jìn)行傳遞，僅僅是為了標(biāo)識(shí)鏈表的實(shí)際情況。

不允許修改?鏈表。

示例：

輸入：head = [3,2,0,-4], pos = 1
輸出：返回索引為 1 的鏈表節(jié)點(diǎn)
解釋：鏈表中有一個(gè)環(huán)，其尾部連接到第二個(gè)節(jié)點(diǎn)。

思路

遇到環(huán)形鏈表問(wèn)題，我們可以先考慮用快慢指針求出相遇點(diǎn)，在這道題中，我們要求出鏈表入環(huán)的第一個(gè)節(jié)點(diǎn)，我們知道鏈表成環(huán)需要尾節(jié)點(diǎn)指向鏈表中的任意節(jié)點(diǎn)，被指向節(jié)點(diǎn)就有了兩個(gè)指向它的節(jié)點(diǎn)，我們可以利用求相交節(jié)點(diǎn)的方法求入環(huán)的第一個(gè)節(jié)點(diǎn)，類似于上面相交鏈表題，為了創(chuàng)造條件，我們可以斷開(kāi)相遇點(diǎn)，創(chuàng)建一個(gè)新節(jié)點(diǎn)newhead，和原節(jié)點(diǎn)head，兩個(gè)節(jié)點(diǎn)帶入上面求相交節(jié)點(diǎn)的題目中，就能求出入環(huán)第一個(gè)節(jié)點(diǎn)了。

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-744158.html

代碼

  //求相交節(jié)點(diǎn)的函數(shù)
struct ListNode *getIntersectionNode(struct ListNode *headA, struct ListNode *headB) {
    struct ListNode* curA=headA;
    struct ListNode* curB=headB;
    int lenA=1,lenB=1;
    while(curA->next)
    {
        curA=curA->next;
        lenA++;
    }
    while(curB->next)
    {
        curB=curB->next;
        lenB++;
    }
    if(curA!=curB)
    return NULL;

int grp=0;
if(lenA>lenB)
grp=lenA-lenB;
else
grp=lenB-lenA;

struct ListNode* longlist=headA,* shortlist = headB;

if(lenA<lenB)
{
    longlist=headB;
    shortlist=headA;
}
//長(zhǎng)的先走差距步
while(grp--)
{
    longlist=longlist->next;
}
while(longlist!=shortlist)
{
    longlist=longlist->next;
    shortlist=shortlist->next;
}
return longlist;
}


struct ListNode *detectCycle(struct ListNode *head) {
    struct ListNode* fast,* slow;
    fast=slow=head;
    while(fast&&fast->next)
    {
        fast=fast->next->next;
        slow=slow->next;
        if(fast==slow)
        {
            struct ListNode* meet=fast;
            //斷開(kāi)相遇點(diǎn)
            struct ListNode* newhead=meet->next;
            meet->next=NULL;
                //找相交節(jié)點(diǎn)
               return getIntersectionNode(newhead,head);
        }
    }
    return NULL;
}

到了這里，關(guān)于[LeetCode]-160. 相交鏈表-141. 環(huán)形鏈表-142.環(huán)形鏈表II-138.隨機(jī)鏈表的復(fù)制的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！