所屬專欄：玩轉(zhuǎn)數(shù)據(jù)結(jié)構(gòu)題型??
?? >博主首頁：初陽785??
?? >代碼托管：chuyang785??
?? >感謝大家的支持，您的點贊和關(guān)注是對我最大的支持?。?！??
?? >博主也會更加的努力，創(chuàng)作出更優(yōu)質(zhì)的博文??！??
?? >關(guān)注我，關(guān)注我，關(guān)注我，重要的事情說三遍?。。。。。。?！??

?? 1.題目來源

LeetCode:復制帶隨機指針的鏈表

??2.題目描述

給你一個長度為 n 的鏈表，每個節(jié)點包含一個額外增加的隨機指針 random ，該指針可以指向鏈表中的任何節(jié)點或空節(jié)點。
構(gòu)造這個鏈表的 深拷貝。 深拷貝應該正好由 n 個 全新 節(jié)點組成，其中每個新節(jié)點的值都設為其對應的原節(jié)點的值。新節(jié)點的 next 指針和 random 指針也都應指向復制鏈表中的新節(jié)點，并使原鏈表和復制鏈表中的這些指針能夠表示相同的鏈表狀態(tài)。復制鏈表中的指針都不應指向原鏈表中的節(jié)點 。
??例如，如果原鏈表中有 X 和 Y 兩個節(jié)點，其中 X.random --> Y 。那么在復制鏈表中對應的兩個節(jié)點 x 和 y ，同樣有 x.random --> y 。
返回復制鏈表的頭節(jié)點。
用一個由 n 個節(jié)點組成的鏈表來表示輸入/輸出中的鏈表。每個節(jié)點用一個 [val, random_index] 表示：
val：一個表示 Node.val 的整數(shù)。
random_index：隨機指針指向的節(jié)點索引（范圍從 0 到 n-1）；如果不指向任何節(jié)點，則為 null 。
你的代碼 只 接受原鏈表的頭節(jié)點 head 作為傳入?yún)?shù)。

??3.解題思路

• 我們分析一下題目的要求：復制一個長度為n的鏈表，其中節(jié)點里面包含了一個val值和一個random隨機指針，這個指針可指向鏈表中的任意一個節(jié)點包括了NULL。
• 如果題目只是要求復制一個長度為n的鏈表，并且復制val值的話就簡單的多了。直接遍歷原鏈表，把值都一一復制過來就行了。但是題目多加了一個條件，就是random值。復制節(jié)點的值很簡單，??但是random是一個指向節(jié)點的指針，當我們復制鏈表的時候，我們新的鏈表節(jié)點的地址肯定是與原鏈表節(jié)點的地址是不一樣的，即使遍歷了原鏈表的random值也找不到新鏈表的random值，?? 所以找到random值是一個難點。
• 那既然這樣我們便可以創(chuàng)建一個長度為n+1的整形數(shù)組，用來記錄每個節(jié)點距離頭節(jié)點的距離包括了NULL。這樣的話我們就可以先遍歷原鏈表，把每個節(jié)點random所指向的值計入到數(shù)組當中，然后復制鏈表的時候，??根據(jù)這個數(shù)組來找到random指向的值。這固然是一種方法，但是他的 空間復雜度：O(n)，時間復雜度：O(n^2)，并不是一個好的解題方法。
• ??那怎么才可以在遍歷原數(shù)組的過程中就可以確定復制鏈表的random值呢？那我們就可以從原鏈表出發(fā)。??于是我們就想到了，如果我們把每個要復制的節(jié)點都插入到被復制節(jié)點的后面（也就是每個原節(jié)點的后面）這樣的話，就很好的解決了找random值這一問題。我們原節(jié)點->random->next == 復制節(jié)點->random。

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

• 完成復制與以及給random賦值完后，就可以把復制節(jié)點斷開，一一鏈接成鏈表，并且恢復原鏈表
  

??4.代碼展示

struct Node* copyRandomList(struct Node* head) 
{

    //第一步，把每個拷貝節(jié)點鏈接到原節(jié)點出
    struct Node* cur = head;
    while (cur)
    {
        struct Node* Next = cur->next;
        //開辟賦值節(jié)點
        struct Node* copyNode = (struct Node*)malloc(sizeof(struct Node));
        //給節(jié)點拷貝val值
        copyNode->val = cur->val;
        cur->next = copyNode;
        copyNode->next = Next;
        cur = Next;
    }
    //第二步，給random賦值
    cur = head;
    while (cur)
    {
        struct Node* copyNode = cur->next;
        if (cur->random == NULL)
        {
            copyNode->random = NULL;
        }
        else
        {
            copyNode->random = cur->random->next;
        }
        cur = copyNode->next;
    }
    //第三步，鏈接賦值鏈表，并恢復原鏈表
    cur = head;
    struct Node* copyhead = NULL, *copyCur = NULL;
    while (cur)
    {
        struct Node* copy = cur->next;
        struct Node* Next = copy->next;

        if (copyhead == NULL)
        {
            copyhead = copyCur = copy;
        }
        else
        {
            copyCur->next = copy;
            copyCur = copyCur->next;
        }
        cur->next = Next;
        cur = Next;
    }

    return copyhead;

}

到了這里，關(guān)于【LeetCode】數(shù)據(jù)結(jié)構(gòu)題解（9）[復制帶隨機指針的鏈表]的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！