Copy List with Random Pointer

Question

  1. A linked list is given such that each node contains an additional random pointer
  2. which could point to any node in the list or null.
  4. Return a deep copy of the list.

题解1 - 哈希表(两次遍历)

首先得弄懂深拷贝的含义，深拷贝可不是我们平时见到的对基本类型的变量赋值那么简单，深拷贝常常用于对象的克隆。这道题要求深度拷贝一个带有 random 指针的链表，random 可能指向空，也可能指向链表中的任意一个节点。

对于通常的单向链表，我们依次遍历并根据原链表的值生成新节点即可，原链表的所有内容便被复制了一份。但由于此题中的链表不只是有 next 指针，还有一个随机指针，故除了复制通常的 next 指针外还需维护新链表中的随机指针。容易混淆的地方在于原链表中的随机指针指向的是原链表中的节点，深拷贝则要求将随机指针指向新链表中的节点。

所有类似的深度拷贝题目的传统做法，都是维护一个 hash table。即先按照复制一个正常链表的方式复制，复制的时候把复制的结点做一个 hash table，以旧结点为 key，新节点为 value。这么做的目的是为了第二遍扫描的时候我们按照这个哈希表把结点的 random 指针接上。

原链表和深拷贝之后的链表如下：

  1. |------------|             |------------|
  2. |            v       ===>  |            v
  3. 1  --> 2 --> 3 --> 4       1' --> 2'--> 3'--> 4'

深拷贝步骤如下；

  1. 根据 next 指针新建链表
  2. 维护新旧节点的映射关系
  3. 拷贝旧链表中的 random 指针
  4. 更新新链表中的 random 指针

其中1, 2, 3 可以合并在一起。

一图胜千文

Hashtable

Python

  1. # Definition for singly-linked list with a random pointer.
  2. # class RandomListNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.next = None
  6. #         self.random = None
  7. class Solution:
  8.     # @param head: A RandomListNode
  9.     # @return: A RandomListNode
  10.     def copyRandomList(self, head):
  11.         dummy = RandomListNode(0)
  12.         curNode = dummy
  13.         randomMap = {}
  15.         while head is not None:
  16.             # link newNode to new List
  17.             newNode = RandomListNode(head.label)
  18.             curNode.next = newNode
  19.             # map old node head to newNode
  20.             randomMap[head] = newNode
  21.             # copy old node random pointer
  22.             newNode.random = head.random
  23.             #
  24.             head = head.next
  25.             curNode = curNode.next
  27.         # re-mapping old random node to new node
  28.         curNode = dummy.next
  29.         while curNode is not None:
  30.             if curNode.random is not None:
  31.                 curNode.random = randomMap[curNode.random]
  32.             curNode = curNode.next
  34.         return dummy.next

C++

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * struct RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode *next, *random;
  6.  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     /**
  12.      * @param head: The head of linked list with a random pointer.
  13.      * @return: A new head of a deep copy of the list.
  14.      */
  15.     RandomListNode *copyRandomList(RandomListNode *head) {
  16.         if (head == NULL) return NULL;
  18.         RandomListNode *dummy = new RandomListNode(0);
  19.         RandomListNode *curNode = dummy;
  20.         unordered_map<RandomListNode *, RandomListNode *> randomMap;
  21.         while(head != NULL) {
  22.             // link newNode to new List
  23.             RandomListNode *newNode = new RandomListNode(head->label);
  24.             curNode->next = newNode;
  25.             // map old node head to newNode
  26.             randomMap[head] = newNode;
  27.             // copy old node random pointer
  28.             newNode->random = head->random;
  30.             head = head->next;
  31.             curNode = curNode->next;
  32.         }
  34.         // re-mapping old random node to new node
  35.         curNode = dummy->next;
  36.         while (curNode != NULL) {
  37.             if (curNode->random != NULL) {
  38.                 curNode->random = randomMap[curNode->random];
  39.             }
  40.             curNode = curNode->next;
  41.         }
  43.         return dummy->next;
  44.     }
  45. };

Java

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * class RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode next, random;
  6.  *     RandomListNode(int x) { this.label = x; }
  7.  * };
  8.  */
  9. public class Solution {
  10.     /**
  11.      * @param head: The head of linked list with a random pointer.
  12.      * @return: A new head of a deep copy of the list.
  13.      */
  14.     public RandomListNode copyRandomList(RandomListNode head) {
  15.         if (head == null) return null;
  17.         RandomListNode dummy = new RandomListNode(0);
  18.         RandomListNode curNode = dummy;
  19.         HashMap<RandomListNode, RandomListNode> randomMap = new HashMap<RandomListNode, RandomListNode>();
  20.         while (head != null) {
  21.             // link newNode to new List
  22.             RandomListNode newNode = new RandomListNode(head.label);
  23.             curNode.next = newNode;
  24.             // map old node head to newNode
  25.             randomMap.put(head, newNode);
  26.             // copy old node random pointer
  27.             newNode.random = head.random;
  28.             //
  29.             head = head.next;
  30.             curNode = curNode.next;
  31.         }
  33.         // re-mapping old random node to new node
  34.         curNode = dummy.next;
  35.         while(curNode != null) {
  36.             if (curNode.random != null) {
  37.                 curNode.random = randomMap.get(curNode.random);
  38.             }
  39.             curNode = curNode.next;
  40.         }
  42.         return dummy.next;
  43.     }
  44. }

源码分析

  1. 只需要一个 dummy 存储新的拷贝出来的链表头，以用来第二次遍历时链接 random 指针。所以第一句异常检测可有可无。
  2. 第一次链接时勿忘记同时拷贝 random 指针，但此时的 random 指针并没有真正“链接”上，实际上是链接到了原始链表的 node 上。
  3. 第二次遍历是为了把原始链表的被链接的 node 映射到新链表中的 node，从而完成真正“链接”。

复杂度分析

总共要进行两次扫描，所以时间复杂度是 O(2n)=O(n), 在链表较长时可能会 TLE(比如 Python). 空间上需要一个哈希表来做结点的映射，所以空间复杂度也是 O(n).

题解2 - 哈希表(一次遍历)

从题解1 的分析中我们可以看到对于 random 指针我们是在第二次遍历时单独处理的，那么在借助哈希表的情况下有没有可能一次遍历就完成呢？我们回想一下题解1 中random 节点的处理，由于在第一次遍历完之前 random 所指向的节点是不知道到底是指向哪一个节点，故我们在将 random 指向的节点加入哈希表之前判断一次就好了(是否已经生成，避免对同一个值产生两个不同的节点)。由于 random 节点也在第一次遍历加入哈希表中，故生成新节点时也需要判断哈希表中是否已经存在。

Python

  1. # Definition for singly-linked list with a random pointer.
  2. # class RandomListNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.next = None
  6. #         self.random = None
  7. class Solution:
  8.     # @param head: A RandomListNode
  9.     # @return: A RandomListNode
  10.     def copyRandomList(self, head):
  11.         dummy = RandomListNode(0)
  12.         curNode = dummy
  13.         hash_map = {}
  15.         while head is not None:
  16.             # link newNode to new List
  17.             if head in hash_map.keys():
  18.                 newNode = hash_map[head]
  19.             else:
  20.                 newNode = RandomListNode(head.label)
  21.                 hash_map[head] = newNode
  22.             curNode.next = newNode
  23.             # map old node head to newNode
  24.             hash_map[head] = newNode
  25.             # copy old node random pointer
  26.             if head.random is not None:
  27.                 if head.random in hash_map.keys():
  28.                     newNode.random = hash_map[head.random]
  29.                 else:
  30.                     newNode.random = RandomListNode(head.random.label)
  31.                     hash_map[head.random] = newNode.random
  32.             #
  33.             head = head.next
  34.             curNode = curNode.next
  36.         return dummy.next

C++

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * struct RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode *next, *random;
  6.  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     /**
  12.      * @param head: The head of linked list with a random pointer.
  13.      * @return: A new head of a deep copy of the list.
  14.      */
  15.     RandomListNode *copyRandomList(RandomListNode *head) {
  16.         RandomListNode *dummy = new RandomListNode(0);
  17.         RandomListNode *curNode = dummy;
  18.         unordered_map<RandomListNode *, RandomListNode *> hash_map;
  19.         while(head != NULL) {
  20.             // link newNode to new List
  21.             RandomListNode *newNode = NULL;
  22.             if (hash_map.count(head) > 0) {
  23.                 newNode = hash_map[head];
  24.             } else {
  25.                 newNode = new RandomListNode(head->label);
  26.                 hash_map[head] = newNode;
  27.             }
  28.             curNode->next = newNode;
  29.             // re-mapping old random node to new node
  30.             if (head->random != NULL) {
  31.                 if (hash_map.count(head->random) > 0) {
  32.                     newNode->random = hash_map[head->random];
  33.                 } else {
  34.                     newNode->random = new RandomListNode(head->random->label);
  35.                     hash_map[head->random] = newNode->random;
  36.                 }
  37.             }
  39.             head = head->next;
  40.             curNode = curNode->next;
  41.         }
  43.         return dummy->next;
  44.     }
  45. };

Java

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * class RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode next, random;
  6.  *     RandomListNode(int x) { this.label = x; }
  7.  * };
  8.  */
  9. public class Solution {
  10.     /**
  11.      * @param head: The head of linked list with a random pointer.
  12.      * @return: A new head of a deep copy of the list.
  13.      */
  14.     public RandomListNode copyRandomList(RandomListNode head) {
  15.         RandomListNode dummy = new RandomListNode(0);
  16.         RandomListNode curNode = dummy;
  17.         HashMap<RandomListNode, RandomListNode> hash_map = new HashMap<RandomListNode, RandomListNode>();
  18.         while (head != null) {
  19.             // link newNode to new List
  20.             RandomListNode newNode = null;
  21.             if (hash_map.containsKey(head)) {
  22.                 newNode = hash_map.get(head);
  23.             } else {
  24.                 newNode = new RandomListNode(head.label);
  25.                 hash_map.put(head, newNode);
  26.             }
  27.             curNode.next = newNode;
  28.             // re-mapping old random node to new node
  29.             if (head.random != null) {
  30.                 if (hash_map.containsKey(head.random)) {
  31.                     newNode.random = hash_map.get(head.random);
  32.                 } else {
  33.                     newNode.random = new RandomListNode(head.random.label);
  34.                     hash_map.put(head.random, newNode.random);
  35.                 }
  36.             }
  37.             //
  38.             head = head.next;
  39.             curNode = curNode.next;
  40.         }
  42.         return dummy.next;
  43.     }
  44. }

源码分析

随机指针指向节点不定，故加入哈希表之前判断一下 key 是否存在即可。C++ 中 C++ 11 引入的 unordered_map 较 map 性能更佳，使用 count 判断 key 是否存在比 find 开销小一点，因为 find 需要构造 iterator。

复杂度分析

遍历一次原链表，判断哈希表中 key 是否存在，故时间复杂度为 O(n), 空间复杂度为 O(n).

题解3 - 间接使用哈希表

上面的解法很显然，需要额外的空间。这个额外的空间是由 hash table 的维护造成的。因为当我们访问一个结点时可能它的 random 指针指向的结点还没有访问过，结点还没有创建，所以需要用 hash table 的额外线性空间维护。

但我们可以通过链表原来结构中的 next 指针来替代 hash table 做哈希。假设有如下链表：

  1. |------------|
  2. |            v
  3. 1  --> 2 --> 3 --> 4

节点1的 random 指向了3。首先我们可以通过 next 遍历链表，依次拷贝节点，并将其添加到原节点后面，如下：

  1. |--------------------------|
  2. |                          v
  3. 1  --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
  4.        |                   ^
  5.        |-------------------|

因为我们只是简单的复制了 random 指针，所以新的节点的 random 指向的仍然是老的节点，譬如上面的1和1’都是指向的3。

调整新的节点的 random 指针，对于上面例子来说，我们需要将1’的 random 指向3’，其实也就是原先 random 指针的next节点。

  1. |--------------------------|
  2. |                          v
  3. 1  --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4'
  4.        |                         ^
  5.        |-------------------------|

最后，拆分链表，就可以得到深度拷贝的链表了。

总结起来，实际我们对链表进行了三次扫描，第一次扫描对每个结点进行复制，然后把复制出来的新节点接在原结点的 next 指针上，也就是让链表变成一个重复链表，就是新旧更替；第二次扫描中我们把旧结点的随机指针赋给新节点的随机指针，因为新结点都跟在旧结点的下一个，所以赋值比较简单，就是 node->next->random = node->random->next，其中 node->next 就是新结点，因为第一次扫描我们就是把新结点接在旧结点后面。现在我们把结点的随机指针都接好了，最后一次扫描我们把链表拆成两个，第一个还原原链表，而第二个就是我们要求的复制链表。因为现在链表是旧新更替，只要把每隔两个结点分别相连，对链表进行分割即可。

Python

  1. # Definition for singly-linked list with a random pointer.
  2. # class RandomListNode:
  3. #     def __init__(self, x):
  4. #         self.label = x
  5. #         self.next = None
  6. #         self.random = None
  7. class Solution:
  8.     # @param head: A RandomListNode
  9.     # @return: A RandomListNode
  10.     def copyRandomList(self, head):
  11.         if head is None:
  12.             return None
  14.         curr = head
  15.         # step1: generate new List with node
  16.         while curr is not None:
  17.             newNode = RandomListNode(curr.label)
  18.             newNode.next = curr.next
  19.             curr.next = newNode
  20.             curr = curr.next.next
  22.         # step2: copy random pointer
  23.         curr = head
  24.         while curr is not None:
  25.             if curr.random is not None:
  26.                 curr.next.random = curr.random.next
  27.             curr = curr.next.next
  28.         # step3: split original and new List
  29.         newHead = head.next
  30.         curr = head
  31.         while curr is not None:
  32.             newNode = curr.next
  33.             curr.next = curr.next.next
  34.             if newNode.next is not None:
  35.                 newNode.next = newNode.next.next
  36.             curr = curr.next
  38.         return newHead

C++

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * struct RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode *next, *random;
  6.  *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
  7.  * };
  8.  */
  9. class Solution {
  10. public:
  11.     /**
  12.      * @param head: The head of linked list with a random pointer.
  13.      * @return: A new head of a deep copy of the list.
  14.      */
  15.     RandomListNode *copyRandomList(RandomListNode *head) {
  16.         if (head == NULL) return NULL;
  18.         RandomListNode *curr = head;
  19.         // step1: generate new List with node
  20.         while (curr != NULL) {
  21.             RandomListNode *newNode = new RandomListNode(curr->label);
  22.             newNode->next = curr->next;
  23.             curr->next = newNode;
  24.             //
  25.             curr = curr->next->next;
  26.         }
  27.         // step2: copy random
  28.         curr = head;
  29.         while (curr != NULL) {
  30.             if (curr->random != NULL) {
  31.                 curr->next->random = curr->random->next;
  32.             }
  33.             curr = curr->next->next;
  34.         }
  35.         // step3: split original and new List
  36.         RandomListNode *newHead = head->next;
  37.         curr = head;
  38.         while (curr != NULL) {
  39.             RandomListNode *newNode = curr->next;
  40.             curr->next = curr->next->next;
  41.             curr = curr->next;
  42.             if (newNode->next != NULL) {
  43.                 newNode->next = newNode->next->next;
  44.             }
  45.         }
  47.         return newHead;
  48.     }
  49. };

Java

  1. /**
  2.  * Definition for singly-linked list with a random pointer.
  3.  * class RandomListNode {
  4.  *     int label;
  5.  *     RandomListNode next, random;
  6.  *     RandomListNode(int x) { this.label = x; }
  7.  * };
  8.  */
  9. public class Solution {
  10.     /**
  11.      * @param head: The head of linked list with a random pointer.
  12.      * @return: A new head of a deep copy of the list.
  13.      */
  14.     public RandomListNode copyRandomList(RandomListNode head) {
  15.         if (head == null) return null;
  17.         RandomListNode curr = head;
  18.         // step1: generate new List with node
  19.         while (curr != null) {
  20.             RandomListNode newNode = new RandomListNode(curr.label);
  21.             newNode.next = curr.next;
  22.             curr.next = newNode;
  23.             //
  24.             curr = curr.next.next;
  25.         }
  26.         // step2: copy random pointer
  27.         curr = head;
  28.         while (curr != null) {
  29.             if (curr.random != null) {
  30.                 curr.next.random = curr.random.next;
  31.             }
  32.             curr = curr.next.next;
  33.         }
  34.         // step3: split original and new List
  35.         RandomListNode newHead = head.next;
  36.         curr = head;
  37.         while (curr != null) {
  38.             RandomListNode newNode = curr.next;
  39.             curr.next = curr.next.next;
  40.             curr = curr.next;
  41.             if (newNode.next != null) {
  42.                 newNode.next = newNode.next.next;
  43.             }
  44.         }
  46.         return newHead;
  47.     }
  48. }

源码分析

注意指针使用前需要判断是否非空，迭代时注意是否前进两步，即.next.next

复杂度分析

总共进行三次线性扫描，所以时间复杂度是 O(n)。但不再需要额外空间的 hash table，所以空间复杂度是 O(1)。

Reference