Daily practice of LeetCode - 138. Copy a linked list with random pointers

前言

Wassup guys！我是Edison

今天是 LeetCode 上的 leetcode 138. 复制带随机指针的链表

Let’s get it！

---

---

1. 题目描述

给你一个长度为 n 的链表,每个节点包含一个额外增加的随机指针 random ,该指针可以指向链表中的任何节点或空节点.
 
构造这个链表的 深拷贝. 深拷贝应该正好由 n 个 全新 节点组成,其中每个新节点的值都设为其对应的原节点的值.
 
新节点的 next 指针和 random 指针也都应指向复制链表中的新节点,并使原链表和复制链表中的这些指针能够表示相同的链表状态.
 
复制链表中的指针都不应指向原链表中的节点 .

示例 1：

示例 2：

2. 思路分析

说实话,I saw this question for the first time,Didn't understand what it meant,The brain is dumbfounded

题目要求我们复制一个长度为 n 的链表,该链表除了每个节点有一个指针指向下一个节点外,还有一个 额外的指针 指向链表中的任意节点或者 null,如下图所示

如何去复制一个带随机指针的链表？

首先我们可以忽略 random 指针,然后对原链表的每个节点进行复制,并追加到原节点的后面,然后再去复制 random 指针.
 
最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原.

图示过程如下：

1、在每个节点的后面加上它的复制,并将原链表和复制链表连在一起（如图所示）.

什么意思呢？

也就是将 拷贝节点 连接在 原节点 后面

2、 从前往后 Traverse each original linked list node,对于有 random 指针的节点 p,我们让它的 p->next->random = p->random->next,也就是说,这样我们就完成了对原链表 random 指针的复刻（如图所示）.

什么意思呢？

拷贝节点的 random 在原节点 random 的后面.
 
p->next It points to the copy node,p is our original node.
 
现在要将 原节点 的 random 拷贝到 拷贝节点 的 random 里面;
 
所以就是 p->next->random = p->random->next.

3、最后我们把 原链表 和 复制链表 拆分出来,并将原链表复原.

也就是说：

把 拷贝节点 拆分下来,linked together to make up 复制链表

3. 实现过程

The biggest difficulty is this 复制随机指针,比如下图中

节点 1 The random pointer points to the node 3
 
节点 3 The random pointer points to the node 2
 
节点 2 的随机指针指向 NULL;

We can solve this problem in three steps

拷贝

根据遍历到的原节点创建对应的新节点,每个新创建的节点是在原节点后面;

比如下图中原节点 1 不再指向原原节点 2,而是指向新节点 1

复制

这一步是最关键的一步,用来设置新链表的随机指针

上图中,我们可以观察到这么一个规律

原节点 1 的随机指针指向原节点 3,新节点 1 的随机指针指向的是原节点 3 的 next
 
原节点 3 的随机指针指向原节点 2,新节点 3 的随机指针指向的是原节点 2 的 next

也就是,原节点 i 的随机指针(如果有的话),指向的是原节点 j

那么新节点 i 的随机指针,指向的是原节点 j 的 next

split and reconnect

只要将两个链表分离开,再返回新链表就可以了

4. 代码实现

接口代码

struct Node* copyRandomList(struct Node* head) {
    
	struct Node* cur = head;
    // 1.拷贝节点链接在原节点的后面
    while (cur) {
    
        struct Node* copy = (struct Node*)malloc(sizeof(struct Node));

        copy->val = cur->val; //Treat it as the original nodeval拷贝到copy节点
        copy->next = cur->next; //put the original nodenext拷贝到copy节点的next
        cur->next = copy; //Then let the original nodenext指向copy节点,Describes the current node andcopy节点连接起来了

        cur = cur->next->next; //开始迭代,cur->next是copy节点,copy->next->next是原链表的第二个节点
    }

    // 2.再次遍历,更新拷贝节点的random
    cur = head; // 继续让cur指向原链表的头节点
    while (cur) {
    
        struct Node* copy = cur->next;

        // ①如果原节点的random为空,那么copy节点的random也为空
        if (cur->random == NULL) {
    
            copy->random = NULL;
        }
        else {
     // ②如果原节点的random的不为空
            copy->random = cur->random->next; // 我的randomequal to yoursrandom的next
        }
        cur = cur->next->next; //Why take two steps？因为cur中间有个copy节点
    }

    // 3.把拷贝节点解下来,链接到一起
    cur = head;
    struct Node* copyHead = NULL, *copyTail = NULL;
    while (cur) {
    
        struct Node* copy = cur->next; // copy节点
        struct Node* next = copy->next; // 原链表的 原节点 的 下一个节点
        cur->next = next; // Reconnect the original linked list
        
        if (copyTail == NULL) {
     // 最开始copyTail是为空的
            copyHead = copyTail = copy; // 直接把copy给它们
        }
        else {
    
            copyTail->next = copy; //At this point, tail insertion is performed
            copyTail = copyTail->next;
        }
        // 原链表的cur节点已经用完了, 让curPoints to the second node of the original linked list
        cur = next;
    }
    //返回 复制链表 的头节点
    return copyHead;
}

提交结果