題目描述：138. 復(fù)制帶隨機指針的鏈表 - 力扣（LeetCode）

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

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

?題解思路：

1. 第一遍循環(huán)：復(fù)制節(jié)點并插入原節(jié)點之后

   在這一步中，我們會遍歷原鏈表，并為每個節(jié)點創(chuàng)建一個新的節(jié)點，然后將新節(jié)點插入到原節(jié)點之后-->插入時可以采用先用新節(jié)點的next指向current的next，在用current的next指向新節(jié)點，最后再將current移動到新節(jié)點的next；如果先將current的next指向新節(jié)點，這樣就還需要保存原節(jié)點的下一個。

2. 第二遍循環(huán)：設(shè)置新節(jié)點的隨機指針

   我們可以根據(jù)原節(jié)點的隨機指針來設(shè)置新節(jié)點的隨機指針。如果原節(jié)點的隨機指針不為空，那么新節(jié)點的隨機指針應(yīng)該指向原節(jié)點隨機指針指向的新節(jié)點（原節(jié)點的下一個節(jié)點）；如果原節(jié)點的隨機指針為空，新節(jié)點的隨機指針指向NULL。

3. 第三遍循環(huán)：拆分鏈表

   在這一步，我們需要將鏈表分成原鏈表和新鏈表。我們遍歷鏈表，將每個新節(jié)點連接到一起，同時恢復(fù)原鏈表的 next 指針-->利用尾插的思想，將新節(jié)點作為尾插節(jié)點進行尾插；

4. 最后返回新鏈表的頭指針。

代碼：

struct Node* creatNode(int val)
{
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->val = val;
    newNode->next = NULL;
    newNode->random = NULL;
    return newNode;
}
struct Node* copyRandomList(struct Node* head) 
{
	// 復(fù)制節(jié)點并插入原節(jié)點之后
    struct Node* current = head;
    while(current)
    {
        struct Node* next = current->next;
        struct Node* newNode = creatNode(current->val);
        newNode->next = current->next;
        current->next = newNode;
        current = next;
    }
    // 設(shè)置新節(jié)點的隨機指針
    current = head;
    while(current)
    {
        struct Node* newNode = current->next;
        if(current->random != NULL)
        {
            newNode->random = current->random->next;
        }
        else
        {
            newNode->random = NULL;
        }
        current = newNode->next;
    }
    // 拆分鏈表
    struct Node* newHead = NULL, *newTail = NULL; 
    current = head;
    while(current)
    {
        struct Node* newNode = current->next;
        struct Node* next = newNode->next;
        // 尾插
        if(newTail == NULL)
        {
            newHead = newTail = newNode;
        }
        else
        {
            newTail->next = newNode;
            newTail = newNode;
        }
        current->next = next; // 恢復(fù)原鏈表的 next 指針
        current = next;
    }
    return newHead;
}

注：（第一步圖解）

本次內(nèi)容到此結(jié)束了！如果你覺得這篇博客對你有幫助的話 ，希望你能夠給我點個贊，鼓勵一下我。感謝感謝……文章來源地址http://www.zghlxwxcb.cn/news/detail-639718.html

到了這里，關(guān)于138. 復(fù)制帶隨機指針的鏈表（深拷貝）題解的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！