138. Copy List with Random Pointer - cocoder39/coco39_LC GitHub Wiki

138. Copy List with Random Pointer

Notes 2024: Option 1.1: iterative copy by leveraging hashmap (additional O(N) space)

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        visited = {}
        old_node = head
        while old_node:
            new_node = self.getClonedNode(visited, old_node)
            new_node.random = self.getClonedNode(visited, old_node.random)
            new_node.next = self.getClonedNode(visited, old_node.next)
            old_node = old_node.next
        return self.getClonedNode(visited, head)
    
    def getClonedNode(self, visited: dict, node: 'Node') -> 'Node':
        if not node:
            return None
        
        if node not in visited:
            visited[node] = Node(node.val)
        return visited[node]

Option 1.2: recursive copy by leveraging hashmap (additional O(N) space)

class Solution:
    def __init__(self):
        self.visited = {}

    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None

        if head in self.visited:
            return self.visited[head]
        
        copy = Node(head.val)
        self.visited[head] = copy

        copy.next = self.copyRandomList(head.next)
        copy.random = self.copyRandomList(head.random)
        return copy

Option 2: 3-pass solution to manipulate linked list (O(1) extra memory)

instead of using hashmap to associate copy with original node, it inserts the copy in between original node and original_node.next.

class Solution:
    def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
        if not head:
            return None
        
        old_node = head
        while old_node:
            new_node = Node(old_node.val)
            new_node.next = old_node.next
            old_node.next = new_node
            old_node = new_node.next
        
        old_node = head
        while old_node:
            new_node = old_node.next
            new_node.random = old_node.random.next if old_node.random else None
            old_node = new_node.next
        
        old_node = head
        new_head = Node(0)
        new_cur = new_head
        while old_node:
            new_node = old_node.next
            old_node.next = new_node.next
            new_node.next = old_node.next.next if old_node.next else None
            
            old_node = old_node.next
            new_cur.next = new_node
            new_cur = new_cur.next
        
        return new_head.next

====================================================== solution 1: without using extra memory

RandomListNode *copyRandomList(RandomListNode *head) {
        //copy and insert
        RandomListNode* p = head;
        while (p) {
            RandomListNode* copy = new RandomListNode(p->label);
            copy->next = p->next;
            p->next = copy;
            p = copy->next;
        }
        
        //link to random pointer
        p = head;
        while (p) {
            RandomListNode* copy = p->next;
            if (p->random) //attention
                copy->random = p->random->next;
            p = copy->next;
        }
        
        //split
        p = head;
        RandomListNode dummy(0);
        RandomListNode* p1 = &dummy;
        while (p) {
            RandomListNode* copy = p->next;
            p1->next = copy;
            p->next = copy->next;
            if (copy->next) //attention
                copy->next = copy->next->next;
            p = p->next;
            p1 = p1->next;
        }
        return dummy.next;
    }

solution 2: traversal -> create new + mapping -> link

• 1. copy list with assigning random pointers with default value, only create each node first then you can guarantee the random node already exists in the copied list
• 2. map nodes in original list to nodes in copied list, then the random nodes in original list are mapped to random nodes in copied list. copy_node->random = map[original_node->random] since we have map[original_node] = copy_node;

O(N) extra memory

RandomListNode *copyRandomList(RandomListNode *head) {
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode dummy(0);
        RandomListNode* p1 = head;
        RandomListNode* p2 = &dummy;
        while (p1) {
            RandomListNode* copy = new RandomListNode(p1->label);
            map[p1] = copy; // map original node to copy node
            p2->next = copy;
            p2 = p2->next;
            p1 = p1->next;
        }
        
        p1 = head;
        p2 = dummy.next;
        while (p1) {
            RandomListNode* randomNode = p1->random;
            p2->random = map[randomNode]; // random to random
            p1 = p1->next;
            p2 = p2->next;
        } 
        return dummy.next;
    }