【鏈表OJ】Leetcode 138. 復制帶隨機指標的鏈表（集大成者）-有解無憂

題目鏈接

解題思路

此題可以分為三步進行：

拷貝鏈表的每一個結點，拷貝的結點先鏈接到被拷貝結點后面
復制隨機指標的鏈接：拷貝結點的隨機指標指向被拷貝結點隨機指標的下一個位置
拆解鏈表，把拷貝的鏈表從原鏈表中拆解出來

第一步

拷貝鏈表的每一個結點，拷貝的結點先鏈接到被拷貝結點后面，

在這里插入圖片描述
需要注意 copy 結點插入時，指標先后順序，避免結點脫鉤，

// 將新結點插入到原鏈表每一個結點后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = BuyListNode(cur->val);
        struct Node* next = cur->next;
        
        copy->next = next;
        cur->next = copy;
        // 迭代
        cur = next;
    }

第二步

復制隨機指標的鏈接：拷貝結點的隨機指標指向被拷貝結點隨機指標的下一個位置，

注意看藍色畫圖部分，即為如何查找到random指標，

在這里插入圖片描述
最終鏈接結果

在這里插入圖片描述

// 根據原結點的random，處理復制結點的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next, *next = copy->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;

        cur = next;
    }

第三步

拆解鏈表，把拷貝的鏈表從原鏈表中拆解出來，

這里使用不帶哨兵位的鏈表構造方法帶哨兵位講解指路：分割鏈表
在這里插入圖片描述

// 解綁新結點，恢復舊鏈表連接關系
    struct Node* newhead, *newtail;
    newhead = newtail = NULL;

    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next, *next = copy->next;

        // 對新鏈
        if(newhead == NULL)
        {
            newhead = copy;
            newtail = copy;
        }
        else
        {
            newtail->next = copy;
            newtail = copy;
        }

        // 對舊鏈
        cur->next = next;
        cur = next;
    }

具體實作思路和尾插結點無異，不會的可以看這一篇不帶哨兵位單向鏈表

AC程式

/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
struct Node* BuyListNode(int x) {
    struct Node* copy = (struct Node*)malloc(sizeof(struct Node));
    copy->val = x;
    copy->random = NULL;
    copy->next = NULL;
    return copy;
}

struct Node* copyRandomList(struct Node* head) {
	// 將新結點插入到原鏈表每一個結點后面
    struct Node* cur = head;
    while(cur)
    {
        struct Node* copy = BuyListNode(cur->val);
        struct Node* next = cur->next;
        copy->next = next;
        cur->next = copy;
        cur = next;
    }

    // 根據原結點的random，處理復制結點的random
    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next, *next = copy->next;
        if(cur->random == NULL)
            copy->random = NULL;
        else
            copy->random = cur->random->next;

        cur = next;
    }

    // 解綁新結點，恢復舊鏈表連接關系
    struct Node* newhead, *newtail;
    newhead = newtail = NULL;

    cur = head;
    while(cur)
    {
        struct Node* copy = cur->next, *next = copy->next;

        // 對新鏈
        if(newhead == NULL)
        {
            newhead = copy;
            newtail = copy;
        }
        else
        {
            newtail->next = copy;
            newtail = copy;
        }

        // 對舊鏈
        cur->next = next;
        cur = next;
    }

    return newhead;
}

轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/339152.html

標籤：其他

上一篇：堆的基本知識

下一篇：網路基本概念總結