Last Updated on 2022-03-12 by Clay
題目
A linked list of lengthnis given such that each node contains an additional random pointer, which could point to any node in the list, ornull. Construct a deep copy of the list. The deep copy should consist of exactlynbrand new nodes, where each new node has its value set to the value of its corresponding original node. Both thenextandrandompointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list. For example, if there are two nodesXandYin the original list, whereX.random --> Y, then for the corresponding two nodesxandyin the copied list,x.random --> y. Return the head of the copied linked list.The linked list is represented in the input/output as a list ofnnodes. Each node is represented as a pair of[val, random_index]where: -val: an integer representingNode.val-random_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif it does not point to any node. Your code will only be given theheadof the original linked list.
Example 1:
Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]
Example 2:
Input: head = [[1,1],[2,1]] Output: [[1,1],[2,1]]
Example 3:
Input: head = [[3,null],[3,0],[3,null]] Output: [[3,null],[3,0],[3,null]]
Constraints:
0 <= n <= 1000-104 <= Node.val <= 104Node.randomisnullor is pointing to some node in the linked list.
題目輸入一個 Node 結構的資料，Node 除了有指向下一個 Node 的 next 屬性外，還另外有一個隨機指向鏈結串列中某個節點的 random 屬性。
而我們要做的，就是所謂的深複製（deep copy），將這個鏈結串列完整地複製另外一份，並將其回傳。
解題思路
一開始，我直接遍歷展開原本的 head 節點，並將所有節點的 next 以及 random 都繼續展開，但很快地就發現因為 random 會隨機指向節點，所以會造成無窮迴圈。所以解決方法應為『紀錄製造過的節點』。
接著，我使用 val 屬性對應 Node 節點的方式使用字典儲存，但很快就發現不同節點的 val 屬性值可能會相同。
最後我乾脆地使用原始串列的 Node 對應複製後的 Node，因為我們可以透過只遍歷一次原始串列的 Node 找到每個 pointer 。
複雜度
只需要遍歷一次，但是卻需要把每個節點都儲存起來…… 所以兩個複雜度都是 O(n)。
| Time complexity | O(n) |
| Space complexity | O(n) |
C++ 範例程式碼
/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
// Base case
if (head == nullptr) return nullptr;
// Init
Node* curr = new Node(head->val);
Node* result = new Node(0, curr);
unordered_map<Node*, Node*> map({{head, result->next}});
// Traversal
while (head != nullptr) {
// Next part
if (head->next == nullptr) {
curr->next = nullptr;
}
else if (map.count(head->next)) {
curr->next = map[head->next];
}
else {
curr->next = new Node(head->next->val);
map[head->next] = curr->next;
}
// Random part
if (head->random == nullptr) {
curr->random = nullptr;
}
else if (map.count(head->random)) {
curr->random = map[head->random];
}
else {
curr->random = new Node(head->random->val);
map[head->random] = curr->random;
}
// Step
head = head->next;
curr = curr->next;
}
return result->next;
}
};Python 範例程式碼
"""
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
"""
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# Base case
if not head: return None
# Init
curr = Node(head.val)
result = Node(0, curr)
mp = {head: result.next}
# Traversal
while head:
# Next part
if not head.next:
curr.next = None
elif head.next in mp:
curr.next = mp[head.next]
else:
curr.next = Node(head.next.val)
mp[head.next] = curr.next
# Random part
if not head.random:
curr.random = None
elif head.random in mp:
curr.random = mp[head.random]
else:
curr.random = Node(head.random.val)
mp[head.random] = curr.random
# Step
head = head.next
curr = curr.next
return result.next