2021-03-01 | 138. 复制带随机指针的链表

小咪咪 2022-11-13 01:56 108阅读 0赞

### 1. 题目描述 ###

给你一个长度为 `n` 的链表，每个节点包含一个额外增加的随机指针 `random` ，该指针可以指向链表中的任何节点或空节点。

构造这个链表的 **[深拷贝][Link 1]**。 深拷贝应该正好由 `n` 个 **全新** 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 `next` 指针和 `random` 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。\*\*复制链表中的指针都不应指向原链表中的节点 \*\*。

例如，如果原链表中有 `X` 和 `Y` 两个节点，其中 `X.random --> Y` 。那么在复制链表中对应的两个节点 `x` 和 `y` ，同样有 `x.random --> y` 。  
返回复制链表的头节点。

用一个由 `n` 个节点组成的链表来表示输入/输出中的链表。每个节点用一个 `[val, random_index]` 表示：

*  `val`：一个表示 `Node.val` 的整数。
 *  `random_index`：随机指针指向的节点索引（范围从 `0` 到 `n-1`）；如果不指向任何节点，则为 `null` 。

你的代码 **只** 接受原链表的头节点 `head` 作为传入参数。

**示例 1：**  
![在这里插入图片描述][20210324233432673.png]

输入：head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
    输出：[[7,null],[13,0],[11,4],[10,2],[1,0]]

**示例 2：**  
![在这里插入图片描述][2021032423344081.png]

输入：head = [[1,1],[2,1]]
    输出：[[1,1],[2,1]]

**示例 3：**  
![在这里插入图片描述][20210324233453306.png]

输入：head = [[3,null],[3,0],[3,null]]
    输出：[[3,null],[3,0],[3,null]]

**示例 4：**

输入：head = []
    输出：[]
    解释：给定的链表为空（空指针），因此返回 null。

**提示：**

*  `0 <= n <= 1000`
 *  `-10000 <= Node.val <= 10000`
 *  `Node.random` 为空（null）或指向链表中的节点。

### 2. 解题思路 ###

对于这道题目，我们可以用三步走来搞定这个问题：

1）第一步，根据遍历到的原节点创建对应的新节点，每个新创建的节点是在原节点后面，比如下图中原节点1不再指向原原节点2，而是指向新节点1  
![在这里插入图片描述][20210324233543169.png]

2）第二步是最关键的一步，用来设置新链表的随机指针  
![在这里插入图片描述][20210324233532132.png]

上图中，可以看到一个规律

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

也就是，原节点i的随机指针(如果有的话)，指向的是原节点j。那么新节点i的随机指针，指向的是原节点j的next。

3）第三步只要将两个链表分离开，再返回新链表就可以了  
![在这里插入图片描述][20210324233518779.png]

**复杂度分析：**

*  时间复杂度：O(n)，其中 n 是链表中节点的数目，我们需要遍历整个链表。
 *  空间复杂度：O(n)，这里我们只需要常量的空间。

### 3. 代码实现 ###

/** * // Definition for a Node. * function Node(val, next, random) { * this.val = val; * this.next = next; * this.random = random; * }; */
    
    /** * @param {Node} head * @return {Node} */
    var copyRandomList = function(head) { 
        if(!head){ 
            return null
        }
    
        let p = head
        // 在每个原节点后面创建一个新节点
        while(p !== null){ 
            let newNode = new Node(p.val)
            newNode.next = p.next
            p.next = newNode
            p = newNode.next
        }
        p = head
        // 设置新节点的随机节点
        while(p !== null){ 
            if(p.random){ 
                p.next.random = p.random.next
            }
            p = p.next.next
        }
        let dummyHead = new Node(-1)
        p = head
        let cur = dummyHead
        // 将两个链表分离
        while(p !== null){ 
            cur.next = p.next
            cur = cur.next
            p.next = cur.next
            p = p.next
        }
        return dummyHead.next
    };

### 4. 提交结果 ###

![在这里插入图片描述][2021032423360190.png]

[Link 1]: https://baike.baidu.com/item/%E6%B7%B1%E6%8B%B7%E8%B4%9D/22785317?fr=aladdin
[20210324233432673.png]: /images/20221022/abb11f58f951442baeb38e852836a7b2.png?
[2021032423344081.png]: /images/20221022/0d2cb6d069f4416bb7ce625d29aef9a6.png?
[20210324233453306.png]: /images/20221022/329b812fff1e470e85ee32da6d4d1681.png?
[20210324233543169.png]: https://img-blog.csdnimg.cn/20210324233543169.png
[20210324233532132.png]: https://img-blog.csdnimg.cn/20210324233532132.png?
[20210324233518779.png]: https://img-blog.csdnimg.cn/20210324233518779.png?
[2021032423360190.png]: https://img-blog.csdnimg.cn/2021032423360190.png?