题目

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

The Linked List is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) where random pointer points to, or null if it does not point to any node.

Example 1:
image.png

  1. Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
  2. Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:
image.png

  1. Input: head = [[1,1],[2,1]]
  2. Output: [[1,1],[2,1]]

Example 3:
image.png
**

  1. Input: head = [[3,null],[3,0],[3,null]]
  2. Output: [[3,null],[3,0],[3,null]]

Example 4:

  1. Input: head = []
  2. Output: []
  3. Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

  • -10000 <= Node.val <= 10000
  • Node.random is null or pointing to a node in the linked list.
  • Number of Nodes will not exceed 1000.

题意

给定一个链表，该链表中有next和random两个域，next指向链表的下一个结点，random指向链表中随机一个结点或为null。要求返回该链表的一个深拷贝。

思路

拷贝next容易，难在拷贝random。问题的关键在于如何建立新旧链表对应结点之间的关系。

一种非常巧妙地方法是，每次拷贝一个结点A’后，将其插入到旧链表对应结点A之后，以此建立对应关系A->A’，即A.next = A'。如果有A.random = B，且A'.random = B'，根据之前建立的对应关系还能得到B.next = B'，所以很容易发现A'.random = A.random.next。拷贝完所有的random后，只要再将新旧链表拆分出来即可。
image.png

也可以使用HashMap来绑定新旧结点，这样更加直观一点。
image.png

代码实现

Java

链表交叉

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         // 将新结点交叉插入到旧链表中
  4.         Node p = head;
  5.         while (p != null) {
  6.             Node temp = new Node(p.val);
  7.             temp.next = p.next;
  8.             p.next = temp;
  9.             p = temp.next;
  10.         }
  12.         // 生成新链表的random域
  13.         p = head;
  14.         while (p != null) {
  15.             Node q = p.next;
  16.             q.random = p.random == null ? null : p.random.next;        // null单独处理
  17.             p = q.next;
  18.         }
  20.         // 拆分新旧链表
  21.         p = head;
  22.         Node dummy = new Node(0);
  23.         Node cur = dummy;
  24.         while (p != null) {
  25.             cur.next = p.next;
  26.             cur = cur.next;
  27.             p.next = cur.next;
  28.             p = p.next;
  29.             cur.next = null;
  30.         }
  32.         return dummy.next;
  33.     }
  34. }

Hash

  1. class Solution {
  2.     public Node copyRandomList(Node head) {
  3.         Map<Node, Node> hash = new HashMap<>();
  4.         Node p = head;
  5.         Node dummy = new Node(0);
  6.         Node cur = dummy;
  8.         // 生成hash对应关系
  9.         while (p != null) {
  10.             cur.next = new Node(p.val);
  11.             cur = cur.next;
  12.             hash.put(p, cur);
  13.             p = p.next;
  14.         }
  16.         // 根据对应关系生成新链表的random域
  17.         p = head;
  18.         while (p != null) {
  19.             hash.get(p).random = p.random == null ? null : hash.get(p.random);    // null单独处理
  20.             p = p.next;
  21.         }
  23.         return dummy.next;
  24.     }
  25. }

JavaScript

  1. /**
  2.  * @param {Node} head
  3.  * @return {Node}
  4.  */
  5. var copyRandomList = function (head) {
  6.   let p = head
  7.   while (p) {
  8.     p.next = new Node(p.val, p.next, null)
  9.     p = p.next.next
  10.   }
  11.   p = head
  12.   while (p) {
  13.     p.next.random = p.random ? p.random.next : null
  14.     p = p.next.next
  15.   }
  16.   const dummy = new Node(0, null, null)
  17.   p = dummy
  18.   while (head) {
  19.     p.next = head.next
  20.     p = p.next
  21.     head.next = head.next.next
  22.     head = head.next
  23.   }
  24.   return dummy.next
  25. }