Clone Linked List

1class Node:
2    def __init__(self, val, next=None, random=None):
3        self.val = val
4        self.next = next
5        self.random = random
6 
7def copyRandomList(head):
8    if not head:
9        return None
10 
11    # Step 1: Create copy nodes and weave them in
12    curr = head
13    while curr:
14        copy = Node(curr.val)
15        copy.next = curr.next
16        curr.next = copy
17        curr = copy.next
18 
19    # Step 2: Set random pointers for copies
20    curr = head
21    while curr:
22        if curr.random:
23            curr.next.random = curr.random.next
24        curr = curr.next.next
25 
26    # Step 3: Separate the two lists
27    curr = head
28    copy_head = head.next
29    while curr:
30        copy = curr.next
31        curr.next = copy.next
32        curr = copy.next
33        if curr:
34            copy.next = curr.next
35 
36    return copy_head