Copy List with Random Pointer
- 2 min read
- LC-Medium
- Linked List
3 years ago
Solution
- The immediate problem here is the fact that if you do it in one pass, thanks to the random pointer, you'd have to point to nodes that weren't yet created
- For example, the node 11's random points to node 1. But this is a linked list, and we're going iteratively node by node, so the new copy of the node 1 does not exist yet.
- This is solved by using two passes and a hashmap
- In the first pass, create copies of all the nodes. Store in hashmap where key is old node and value is new node.
- In second pass, assign next's and random's of new node using old node values from the hashmap.
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
# Create copies of all nodes
copies = {None: None}
cur = head
while cur:
copies[cur] = Node(cur.val)
cur = cur.next
# Form new list connections
cur = head
while cur:
copies[cur].next = copies[cur.next]
copies[cur].random = copies[cur.random]
cur = cur.next
return copies[head]
Recursive Solution
- Kinda similar to Clone Graph
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
refs = {None: None}
def copy(node):
if node not in refs:
new_node = Node(node.val)
refs[node] = new_node
new_node.next = copy(node.next)
new_node.random = copy(node.random)
return refs[node]
return copy(head)