Copy List with Random Pointer · 數據結構與算法/leetcode/lintcode題解

# Copy List with Random Pointer ### Source - leetcode: [Copy List with Random Pointer | LeetCode OJ](https://leetcode.com/problems/copy-list-with-random-pointer/) - lintcode: [(105) Copy List with Random Pointer](http://www.lintcode.com/en/problem/copy-list-with-random-pointer/) ~~~ 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. ~~~ ### 題解1 - 哈希表(兩次遍歷) 首先得弄懂深拷貝的含義，深拷貝可不是我們平時見到的對基本類型的變量賦值那么簡單，深拷貝常常用于對象的克隆。這道題要求**深度拷貝**一個帶有 random 指針的鏈表，random 可能指向空，也可能指向鏈表中的任意一個節點。對于通常的單向鏈表，我們依次遍歷并根據原鏈表的值生成新節點即可，原鏈表的所有內容便被復制了一份。但由于此題中的鏈表不只是有 next 指針，還有一個隨機指針，故除了復制通常的 next 指針外還需維護新鏈表中的隨機指針。容易混淆的地方在于原鏈表中的隨機指針指向的是原鏈表中的節點，深拷貝則要求將隨機指針指向新鏈表中的節點。所有類似的**深度拷貝**題目的傳統做法，都是維護一個 `hash table`。即先按照復制一個正常鏈表的方式復制，復制的時候把復制的結點做一個 `hash table`，以舊結點為 key，新節點為 value。這么做的目的是為了第二遍掃描的時候我們按照這個哈希表把結點的 random 指針接上。原鏈表和深拷貝之后的鏈表如下： ~~~ |------------| |------------| | v ===> | v 1 --> 2 --> 3 --> 4 1' --> 2'--> 3'--> 4' ~~~ 深拷貝步驟如下； 1. 根據 next 指針新建鏈表 1. 維護新舊節點的映射關系 1. 拷貝舊鏈表中的 random 指針 1. 更新新鏈表中的 random 指針其中1, 2, 3 可以合并在一起。一圖勝千文 ![Hashtable](https://box.kancloud.cn/2015-10-24_562b1f4ebe935.jpg) ### Python ~~~ # Definition for singly-linked list with a random pointer. # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # @param head: A RandomListNode # @return: A RandomListNode def copyRandomList(self, head): dummy = RandomListNode(0) curNode = dummy randomMap = {} while head is not None: # link newNode to new List newNode = RandomListNode(head.label) curNode.next = newNode # map old node head to newNode randomMap[head] = newNode # copy old node random pointer newNode.random = head.random # head = head.next curNode = curNode.next # re-mapping old random node to new node curNode = dummy.next while curNode is not None: if curNode.random is not None: curNode.random = randomMap[curNode.random] curNode = curNode.next return dummy.next ~~~ ### C++ ~~~ /** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */ class Solution { public: /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ RandomListNode *copyRandomList(RandomListNode *head) { if (head == NULL) return NULL; RandomListNode *dummy = new RandomListNode(0); RandomListNode *curNode = dummy; unordered_map<RandomListNode *, RandomListNode *> randomMap; while(head != NULL) { // link newNode to new List RandomListNode *newNode = new RandomListNode(head->label); curNode->next = newNode; // map old node head to newNode randomMap[head] = newNode; // copy old node random pointer newNode->random = head->random; head = head->next; curNode = curNode->next; } // re-mapping old random node to new node curNode = dummy->next; while (curNode != NULL) { if (curNode->random != NULL) { curNode->random = randomMap[curNode->random]; } curNode = curNode->next; } return dummy->next; } }; ~~~ ### Java ~~~ /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ public RandomListNode copyRandomList(RandomListNode head) { if (head == null) return null; RandomListNode dummy = new RandomListNode(0); RandomListNode curNode = dummy; HashMap<RandomListNode, RandomListNode> randomMap = new HashMap<RandomListNode, RandomListNode>(); while (head != null) { // link newNode to new List RandomListNode newNode = new RandomListNode(head.label); curNode.next = newNode; // map old node head to newNode randomMap.put(head, newNode); // copy old node random pointer newNode.random = head.random; // head = head.next; curNode = curNode.next; } // re-mapping old random node to new node curNode = dummy.next; while(curNode != null) { if (curNode.random != null) { curNode.random = randomMap.get(curNode.random); } curNode = curNode.next; } return dummy.next; } } ~~~ ### 源碼分析 1. 只需要一個 `dummy` 存儲新的拷貝出來的鏈表頭，以用來第二次遍歷時鏈接 random 指針。所以第一句異常檢測可有可無。 1. 第一次鏈接時勿忘記同時拷貝 random 指針，但此時的 random 指針并沒有真正“鏈接”上，實際上是鏈接到了原始鏈表的 node 上。 1. 第二次遍歷是為了把原始鏈表的被鏈接的 node 映射到新鏈表中的 node，從而完成真正“鏈接”。 ### 復雜度分析總共要進行兩次掃描，所以時間復雜度是 O(2n)=O(n)O(2n)=O(n)O(2n)=O(n), 在鏈表較長時可能會 [TLE](# "Time Limit Exceeded 的簡稱。你的程序在 OJ 上的運行時間太長了，超過了對應題目的時間限制。")(比如 Python). 空間上需要一個哈希表來做結點的映射，所以空間復雜度也是 O(n)O(n)O(n). ### 題解2 - 哈希表(一次遍歷) 從題解1 的分析中我們可以看到對于 random 指針我們是在第二次遍歷時單獨處理的，那么在借助哈希表的情況下有沒有可能一次遍歷就完成呢？我們回想一下題解1 中random 節點的處理，由于在第一次遍歷完之前 random 所指向的節點是不知道到底是指向哪一個節點，故我們在將 random 指向的節點加入哈希表之前判斷一次就好了(是否已經生成，避免對同一個值產生兩個不同的節點)。由于 random 節點也在第一次遍歷加入哈希表中，故生成新節點時也需要判斷哈希表中是否已經存在。 ### Python ~~~ # Definition for singly-linked list with a random pointer. # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # @param head: A RandomListNode # @return: A RandomListNode def copyRandomList(self, head): dummy = RandomListNode(0) curNode = dummy hash_map = {} while head is not None: # link newNode to new List if head in hash_map.keys(): newNode = hash_map[head] else: newNode = RandomListNode(head.label) hash_map[head] = newNode curNode.next = newNode # map old node head to newNode hash_map[head] = newNode # copy old node random pointer if head.random is not None: if head.random in hash_map.keys(): newNode.random = hash_map[head.random] else: newNode.random = RandomListNode(head.random.label) hash_map[head.random] = newNode.random # head = head.next curNode = curNode.next return dummy.next ~~~ ### C++ ~~~ /** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */ class Solution { public: /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ RandomListNode *copyRandomList(RandomListNode *head) { RandomListNode *dummy = new RandomListNode(0); RandomListNode *curNode = dummy; unordered_map<RandomListNode *, RandomListNode *> hash_map; while(head != NULL) { // link newNode to new List RandomListNode *newNode = NULL; if (hash_map.count(head) > 0) { newNode = hash_map[head]; } else { newNode = new RandomListNode(head->label); hash_map[head] = newNode; } curNode->next = newNode; // re-mapping old random node to new node if (head->random != NULL) { if (hash_map.count(head->random) > 0) { newNode->random = hash_map[head->random]; } else { newNode->random = new RandomListNode(head->random->label); hash_map[head->random] = newNode->random; } } head = head->next; curNode = curNode->next; } return dummy->next; } }; ~~~ ### Java ~~~ /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ public RandomListNode copyRandomList(RandomListNode head) { RandomListNode dummy = new RandomListNode(0); RandomListNode curNode = dummy; HashMap<RandomListNode, RandomListNode> hash_map = new HashMap<RandomListNode, RandomListNode>(); while (head != null) { // link newNode to new List RandomListNode newNode = null; if (hash_map.containsKey(head)) { newNode = hash_map.get(head); } else { newNode = new RandomListNode(head.label); hash_map.put(head, newNode); } curNode.next = newNode; // re-mapping old random node to new node if (head.random != null) { if (hash_map.containsKey(head.random)) { newNode.random = hash_map.get(head.random); } else { newNode.random = new RandomListNode(head.random.label); hash_map.put(head.random, newNode.random); } } // head = head.next; curNode = curNode.next; } return dummy.next; } } ~~~ ### 源碼分析隨機指針指向節點不定，故加入哈希表之前判斷一下 key 是否存在即可。C++ 中 C++ 11 引入的 unordered_map 較 map 性能更佳，使用 count 判斷 key 是否存在比 find 開銷小一點，因為 find 需要構造 iterator。 ### 復雜度分析遍歷一次原鏈表，判斷哈希表中 key 是否存在，故時間復雜度為 O(n)O(n)O(n), 空間復雜度為 O(n)O(n)O(n). ### 題解3 - 間接使用哈希表上面的解法很顯然，需要額外的空間。這個額外的空間是由 `hash table` 的維護造成的。因為當我們訪問一個結點時可能它的 random 指針指向的結點還沒有訪問過，結點還沒有創建，所以需要用 `hash table` 的額外線性空間維護。但我們可以通過鏈表原來結構中的 `next` 指針來替代 `hash table` 做哈希。假設有如下鏈表： ~~~ |------------| | v 1 --> 2 --> 3 --> 4 ~~~ 節點1的 random 指向了3。首先我們可以通過 next 遍歷鏈表，依次拷貝節點，并將其添加到原節點后面，如下： ~~~ |--------------------------| | v 1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4' | ^ |-------------------| ~~~ 因為我們只是簡單的復制了 random 指針，所以新的節點的 random 指向的仍然是老的節點，譬如上面的1和1'都是指向的3。調整新的節點的 random 指針，對于上面例子來說，我們需要將1'的 random 指向3'，其實也就是原先 random 指針的next節點。 ~~~ |--------------------------| | v 1 --> 1' --> 2 --> 2' --> 3 --> 3' --> 4 --> 4' | ^ |-------------------------| ~~~ 最后，拆分鏈表，就可以得到深度拷貝的鏈表了。總結起來，實際我們對鏈表進行了三次掃描，第一次掃描對每個結點進行復制，然后把復制出來的新節點接在原結點的 next 指針上，也就是讓鏈表變成一個重復鏈表，就是新舊更替；第二次掃描中我們把舊結點的隨機指針賦給新節點的隨機指針，因為新結點都跟在舊結點的下一個，所以賦值比較簡單，就是 `node->next->random = node->random->next`，其中 `node->next` 就是新結點，因為第一次掃描我們就是把新結點接在舊結點后面。現在我們把結點的隨機指針都接好了，最后一次掃描我們把鏈表拆成兩個，第一個還原原鏈表，而第二個就是我們要求的復制鏈表。因為現在鏈表是舊新更替，只要把每隔兩個結點分別相連，對鏈表進行分割即可。 ### Python ~~~ # Definition for singly-linked list with a random pointer. # class RandomListNode: # def __init__(self, x): # self.label = x # self.next = None # self.random = None class Solution: # @param head: A RandomListNode # @return: A RandomListNode def copyRandomList(self, head): if head is None: return None curr = head # step1: generate new List with node while curr is not None: newNode = RandomListNode(curr.label) newNode.next = curr.next curr.next = newNode curr = curr.next.next # step2: copy random pointer curr = head while curr is not None: if curr.random is not None: curr.next.random = curr.random.next curr = curr.next.next # step3: split original and new List newHead = head.next curr = head while curr is not None: newNode = curr.next curr.next = curr.next.next if newNode.next is not None: newNode.next = newNode.next.next curr = curr.next return newHead ~~~ ### C++ ~~~ /** * Definition for singly-linked list with a random pointer. * struct RandomListNode { * int label; * RandomListNode *next, *random; * RandomListNode(int x) : label(x), next(NULL), random(NULL) {} * }; */ class Solution { public: /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ RandomListNode *copyRandomList(RandomListNode *head) { if (head == NULL) return NULL; RandomListNode *curr = head; // step1: generate new List with node while (curr != NULL) { RandomListNode *newNode = new RandomListNode(curr->label); newNode->next = curr->next; curr->next = newNode; // curr = curr->next->next; } // step2: copy random curr = head; while (curr != NULL) { if (curr->random != NULL) { curr->next->random = curr->random->next; } curr = curr->next->next; } // step3: split original and new List RandomListNode *newHead = head->next; curr = head; while (curr != NULL) { RandomListNode *newNode = curr->next; curr->next = curr->next->next; curr = curr->next; if (newNode->next != NULL) { newNode->next = newNode->next->next; } } return newHead; } }; ~~~ ### Java ~~~ /** * Definition for singly-linked list with a random pointer. * class RandomListNode { * int label; * RandomListNode next, random; * RandomListNode(int x) { this.label = x; } * }; */ public class Solution { /** * @param head: The head of linked list with a random pointer. * @return: A new head of a deep copy of the list. */ public RandomListNode copyRandomList(RandomListNode head) { if (head == null) return null; RandomListNode curr = head; // step1: generate new List with node while (curr != null) { RandomListNode newNode = new RandomListNode(curr.label); newNode.next = curr.next; curr.next = newNode; // curr = curr.next.next; } // step2: copy random pointer curr = head; while (curr != null) { if (curr.random != null) { curr.next.random = curr.random.next; } curr = curr.next.next; } // step3: split original and new List RandomListNode newHead = head.next; curr = head; while (curr != null) { RandomListNode newNode = curr.next; curr.next = curr.next.next; curr = curr.next; if (newNode.next != null) { newNode.next = newNode.next.next; } } return newHead; } } ~~~ ### 源碼分析注意指針使用前需要判斷是否非空，迭代時注意是否前進兩步，即`.next.next` ### 復雜度分析總共進行三次線性掃描，所以時間復雜度是 O(n)O(n)O(n)。但不再需要額外空間的 `hash table`，所以空間復雜度是 O(1)O(1)O(1)。 ### Reference - [Copy List with Random Pointer - siddontang's leetcode Solution Book](http://siddontang.gitbooks.io/leetcode-solution/content/linked_list/copy_list_with_random_pointer.html/) - [Copy List with Random Pointer 參考程序 Java/C++/Python](http://www.jiuzhang.com/solutions/copy-list-with-random-pointer/) - [Copy List with Random Pointer - Code Ganker](http://blog.csdn.net/linhuanmars/article/details/22463599)