从零学算法138

**138.**给你一个长度为 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]]

•   /*// Definition for a Node.class Node {int val;Node next;Node random;public Node(int val) {this.val = val;this.next = null;this.random = null;}}*/
  

• 我的原始人解法：先遍历一遍链表，复制出没有 random 的链表，与此同时记录下每个原结点对应的复制节点。第二轮遍历的时候复制 random 即可：

•   public Node copyRandomList(Node head) {Map<Node,Node> map = new HashMap<>();// 头部加了一个哑结点Node node = new Node(-1);Node temp = node;Node tempHead = head;while(head!=null){node.next = new Node(head.val);map.put(head,node.next);head=head.next;node=node.next;}head = tempHead;node = temp;while(head!=null){Node random = map.get(head.random);node.next.random = random;head=head.next;node=node.next;}return temp.next;}
  

• 或者可以像他人题解先只是创建每个节点，第二轮遍历的时候直接在 map 中把节点连起来创建链表

•   public Node copyRandomList(Node head) {if(head == null) return null;Node cur = head;Map<Node, Node> map = new HashMap<>();// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射while(cur != null) {map.put(cur, new Node(cur.val));cur = cur.next;}cur = head;// 4. 构建新链表的 next 和 random 指向while(cur != null) {map.get(cur).next = map.get(cur.next);map.get(cur).random = map.get(cur.random);cur = cur.next;}// 5. 返回新链表的头节点return map.get(head);}
  

• 还有个巧妙的思路，构建一个新的拼接链表为：原节点1 -> 新节点1 -> 原节点2 -> 新节点1 ->…。然后你只需要遍历这个链表，新结点的 next 就为该节点的 next 的 next，新结点的 random 就为原结点的 random 的 next。其实这也是一种原节点对应新节点的形式，只不过在 map 中表现为 key->val，在这里表现为 node -> node.next。

•   public Node copyRandomList(Node head) {if(head == null){return null;}// 暂存头结点，待会用来重新遍历Node tempHead = head;// 拼接新链表while(head != null){Node node = new Node(head.val);node.next = head.next;head.next = node;head = node.next;}// 头结点复原，再遍历一遍构建新链表 random 的指向head = tempHead;while(head != null){if(head.random != null){head.next.random = head.random.next;}head = head.next.next;}// 头结点再复原，最后遍历一遍拆分出原链表和结果链表head = tempHead;// 最后结果的头结点，下面用来遍历Node ans = head.next;// 暂存最后结果的头结点Node tempAns = ans;// 构建到尾结点就不构建了，所以是 ans.next != null，也没 next 让你继续构建了while(ans.next != null){// 或者 head.next = head.next.nexthead.next = ans.next;head = head.next;ans.next = head.next;ans = ans.next;}// 原链表尾结点复原head.next = null;return tempAns;}