Leetcode 138 : Copy List with Random Pointer

Solution to Copy List with Random Pointer problem.

See this video for nice explanation of the solution.

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null)
            return head;
        
        Node cur = head;
        
        // Step 1: Create clone nodes A->A`->B->B`
        while(cur != null) {
            Node curClone = new Node(cur.val);
            curClone.next = cur.next;
            cur.next = curClone;
            
            cur = curClone.next;
        }
        
        // Step 2: Connect random nodes
        cur = head;
        while(cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        
        // Step 3: Detach cloned nodes
        Node cloneHead = head.next;
        
        cur = head;
        Node curClone = head.next;
        while(cur != null) {
            cur.next = curClone.next;
            if(cur.next != null) {
                curClone.next = cur.next.next;
            }
            cur = cur.next;
            curClone = curClone.next;
        }
        
        return cloneHead;
    }
}