Copy List with Random Pointer

1public Node copyRandomList(Node head) {
2    if (head == null) return null;
3
4    // Step 1: Create and interleave new nodes
5    Node current = head;
6    while (current != null) {
7        Node newNode = new Node(current.val);
8        newNode.next = current.next;
9        current.next = newNode;
10        current = newNode.next;
11    }
12
13    // Step 2: Assign random pointers
14    current = head;
15    while (current != null) {
16        if (current.random != null) {
17            current.next.random = current.random.next;
18        }
19        current = current.next.next;
20    }
21
22    // Step 3: Separate the lists
23    current = head;
24    Node copiedHead = head.next;
25    while (current != null) {
26        Node copiedNode = current.next;
27        current.next = copiedNode.next;
28        current = current.next;
29        if (current != null) {
30            copiedNode.next = current.next;
31        }
32    }
33
34    return copiedHead;
35}