138. Copy List with Random Pointer (Deep Copy + HashTable + DFS + Interleaving: O(1) S)) 20.3.26 Medium

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.

 

Example 1:



Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.
 

Note:

You must return the copy of the given head as a reference to the cloned list.


Solution: ----------------------------------------------------- Deep Copy + HashTable + DFS
--------------------------------------------------------------- O(n) T, O(n) S
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random)"
        self.val = val
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        self.HashTable = {}                                 # Use a HashTable to avoid copying the same node twice
        return self.dfs(head)
    
    def dfs(self, currnode):
        if not currnode:                                    # IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!!!	
						            # CAN NOT forget to check if the currnode is NONE !!!!
            return None
        if currnode in self.HashTable:
            return self.HashTable[currnode]
        copynode = Node(currnode.val, None, None)           # Also, read the definition for a node carefully,
						            # it is "def __init__(self, val, next, random)", 
							    # so, instead of "copynode = Node(currnode.val)", 
							    # it must be "copynode = Node(currnode.val, None, None)" !!!!
        self.HashTable[currnode] = copynode	            # Store the copynode 
        copynode.next = self.dfs(currnode.next)
        copynode.random = self.dfs(currnode.random)
        return copynode
	
	
Solution no.2: ---------------------------------------- O(1) S interleaving method
"""
# Definition for a Node.
class Node(object):
    def __init__(self, val, next, random):
        self.val = val
        self.next = next
        self.random = random
"""
class Solution(object):
    def copyRandomList(self, head):
        """
        :type head: Node
        :rtype: Node
        """
        if not head:
            return None
        curr = head
        while curr:				                              # Step no.1: interleave old with new
            newNode = Node(curr.val, None, None)
            newNode.next = curr.next
            curr.next = newNode
            curr = curr.next.next
        curr = head
        while curr:						              # Step no.2: assign new.random
            curr.next.random = curr.random.next if curr.random else None      # Must check here, curr.random maybe None
            curr = curr.next.next
        old_LL, new_LL = head, head.next
        return_head = head.next
        while old_LL:				                              # Step no.3: Uninterleave
            old_LL.next = old_LL.next.next
            new_LL.next = new_LL.next.next if new_LL.next else None           # Must check here, new_LL.next maybe None
            old_LL = old_LL.next
            new_LL = new_LL.next
        return return_head


Java Version:
/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {
            return null;
        }
        Map<Node, Node> map = new HashMap<>();
        return clone(head, map);
    }
    
    public Node clone(Node node, Map<Node, Node> map) {
        if (node == null) {
            return null;
        }
        if (map.containsKey(node)) {
            return map.get(node);
        }
        Node currNode = new Node(node.val);
        map.put(node, currNode);
        currNode.next = clone(node.next, map);
        currNode.random = clone(node.random, map);
        return currNode;
    }
}