[路飞]_leetcode-138-复制带随机指针的链表

「这是我参与11月更文挑战的第14天，活动详情查看：2021最后一次更文挑战」

[题目地址][B站地址]

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

构造这个链表的 深拷贝。 深拷贝应该正好由 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：

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

示例 2：

输入： head = [[1,1],[2,1]]
输出： [[1,1],[2,1]]
复制代码

示例 3：

输入： 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）或指向链表中的节点。

复制一个普通的链表很简单，本题的难点在于被复制链表每一个节点有一个 random 指针，指向链表中任意一个节点或者 null

对于这种情况应该如何复制原链表呢？

解题思路如下：

本题解题思路如下：

1. 首先特殊判断如果传入链表为 null,返回 null
2. 在原链表的每个节点后面复制一个新的节点，新节点的 val 等于被复制的节点的 val
3. 将复制节点的 random 指针指向被复制链表节点的 random 指针的 next,如果被复制节点的 random 指针指向 null ,则复制节点的 random 指针同样指向 null
4. 将复制节点从原链表拆分成为单独的链表，即为复制后的链表
5. 返回复制后链表的头节点即可

整体过程如下：

代码如下：

var copyRandomList = function(head) {
  // 特判
  if(head === null) return null;
  let pre = head,next = pre.next;
  // 复制节点
  while(pre){
    pre.next = new Node(pre.val);
    pre.next.next = next;
    pre = next;
    next = pre?pre.next:null;
  }
  // 处理复制后节点的random
  pre = head,next = pre.next;
  while(next){
    next.random = pre.random?pre.random.next:null;
    pre = next.next;
    next = pre?pre.next:null;
  }
  // 获取结果链表的头节点
  const res = head.next;
  // 拆分链表
  pre = head,next = pre.next;
  while(next){
    pre.next = next.next;
    pre = pre.next;
    next.next = pre?pre.next:null;
    next = next.next
  }
  return res;
};
复制代码

至此我们就完成了 leetcode-138-复制带随机指针的链表

如有任何问题或建议，欢迎留言讨论！