目錄

? ? ? 一、升級版的環(huán)形鏈表

? ? ? ? ? 1、題目說明

? ? ? ? ? 2、題目解析

? ? ??二、復制帶隨機指針的鏈表

? ? ? ? ??1、題目說明

? ? ? ? ? 2、題目解析

?

?

一、升級版的環(huán)形鏈表

?1、題目說明

題目鏈接：升級版的環(huán)形鏈表?

給定一個鏈表的頭節(jié)點 head ，返回鏈表開始入環(huán)的第一個節(jié)點。?如果鏈表無環(huán)，則返回NULL。

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

不允許修改?鏈表。

?2、題目解析

這個題的解題思路比較巧妙，經過上一篇博客中環(huán)形鏈表的相交點問題，在這里還是設置快慢指針，讓慢指針從鏈表起始位置開始遍歷鏈表，同時讓快指針從判環(huán)時相遇點的位置開始繞環(huán)運行，兩個指針都是每次均走一步，最終肯定會在入口點的位置相遇。

快指針和慢指針還有關系：

快指針是慢指針的2倍--->2*(L+X) = L+nR+X?

所以，L = nR - X。(n的大小取決于環(huán)的大小，環(huán)越小n越大)?

結論：一個指針從鏈表起始位置運行，一個指針從相遇點位置繞環(huán)，每次都走一步，兩個指針最終會在入口處相遇。

struct ListNode *detectCycle(struct ListNode *head) 
{
    struct ListNode* fast = head,*slow = head;
    while(fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if(slow == fast)
        {
            struct ListNode* meet = slow;
            while(head != meet)
            {
                head = head->next;
                meet = meet->next;
            }
            return meet;
        }
    }
    return  NULL;
}

二、復制帶隨機指針的鏈表(較難)

?1、題目說明

題目鏈接：復制帶隨機指針的鏈表

給你一個長度為 n 的鏈表，每個節(jié)點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。

構造這個鏈表的深拷貝。?深拷貝應該正好由 n 個全新節(jié)點組成，其中每個新節(jié)點的值都設為其對應的原節(jié)點的值。新節(jié)點的 next 指針和 random 指針也都應指向復制鏈表中的新節(jié)點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復制鏈表中的指針都不應指向原鏈表中的節(jié)點?。

用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個[val, random_index]表示：

• val：一個表示 Node.val 的整數(shù)。
• random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1 ）；如果不指向任何節(jié)點，則為 NULL 。

?2、題目解析

將原有鏈表給復制一份，同時原有鏈表的 random 指針是隨機指向某一個節(jié)點的，復制鏈表的同時也要保證該節(jié)點的 random 指針指向的值與原有鏈表的random指向的值不變。

思路如下：

第一步：首先將原有鏈表的每個節(jié)點都拷貝一份放在原節(jié)點的后面。

第二步：設置拷貝節(jié)點的 random，我們用 cur 遍歷原鏈表，cur->random->next 節(jié)點，就是 copy 的 random 要找的節(jié)點。(使用綠色的線表示的)

第三步：我們的復制后的鏈表節(jié)點的random已經處理完畢了，接下來我們將兩個鏈表分割開來，并組成各自新的鏈表。(斷開后，用紫色的線重新組成新的鏈表)

struct Node* copyRandomList(struct Node* head) 
{
    //拷貝節(jié)點,并鏈接在源節(jié)點的后面
	struct Node* cur = head;
    while(cur)
    {
        struct Node* next = cur->next;
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
        copy->val = cur->val;
        //插入鏈接
        cur->next = copy;
        copy->next = next;
        cur = next;
    }
    //設置拷貝節(jié)點的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next;
        if(cur->random ==  NULL)
            copy->random =  NULL;
        else
        {
            copy->random = cur->random->next;
        }
        cur = cur->next->next;
    }
    //拷貝節(jié)點解下來，鏈接組成拷貝鏈表
    cur = head;
    struct Node* copyHead = NULL,*copyTail =NULL;
    while(cur)
    {
        struct Node* copy = cur->next;
        struct Node* next = copy->next;
        cur->next = next;
        //尾插
        if(copyTail ==  NULL)
        {
            copyHead = copyTail = copy;
        }
        else
        {
            copyTail->next = copy;
            copyTail = copyTail->next;
        }
        cur = next;
    }
    return copyHead;
}

?

本文要是有不足的地方，歡迎大家在下面評論，我會在第一時間更正。

文章來源地址http://www.zghlxwxcb.cn/news/detail-794186.html

???老鐵們，記著點贊加關注!!!?

到了這里，關于【數(shù)據(jù)結構】LeetCode升級版的環(huán)形鏈表，復制帶隨機指針的鏈表的文章就介紹完了。如果您還想了解更多內容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！