Skip to content

LeetCode: 138-Copy List with Random Pointer 解題紀錄

Last Updated on 2022-03-12 by Clay

題目

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer 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 nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in 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 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) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of 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 <= 104
  • Node.random is null or is pointing to some node in the linked list.

題目輸入一個 Node 結構的資料,Node 除了有指向下一個 Nodenext 屬性外,還另外有一個隨機指向鏈結串列中某個節點的 random 屬性。

而我們要做的,就是所謂的深複製deep copy),將這個鏈結串列完整地複製另外一份,並將其回傳。


解題思路

一開始,我直接遍歷展開原本的 head 節點,並將所有節點的 next 以及 random 都繼續展開,但很快地就發現因為 random 會隨機指向節點,所以會造成無窮迴圈。所以解決方法應為『紀錄製造過的節點』。

接著,我使用 val 屬性對應 Node 節點的方式使用字典儲存,但很快就發現不同節點的 val 屬性值可能會相同。

最後我乾脆地使用原始串列的 Node 對應複製後的 Node,因為我們可以透過只遍歷一次原始串列的 Node 找到每個 pointer


複雜度

只需要遍歷一次,但是卻需要把每個節點都儲存起來...... 所以兩個複雜度都是 O(n)。

Time complexityO(n)
Space complexityO(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

References


Read More

Leave a Reply