138. Copy List with Random Pointer

https://leetcode.com/problems/copy-list-with-random-pointer/

// 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;
    }
}*/
// My solution: two passes + recursion
/*
class Solution {
    Map<Node,Node> map=new HashMap<>();
    public Node copyRandomList(Node head) {
        Node newHead=copyRandomListUtil(head);
        Node dummy=newHead;
        while(head!=null){
            if(head.random!=null) newHead.random=map.get(head.random);
            head=head.next;
            newHead=newHead.next;
        }
        return dummy;
    } 
    public Node copyRandomListUtil(Node head) {
        if(head==null) return head;
        Node cloneNode=new Node(head.val);
        map.put(head,cloneNode);
        cloneNode.next=copyRandomListUtil(head.next);  
        return cloneNode;
    }
}*/

// Solution from leetcode: recursion + one pass
// Time Complexity : O(N), Space Complexity : O(N)
class Solution {
    Map<Node,Node> map=new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head==null) return head;
        if(map.containsKey(head)) return map.get(head);
        Node cloneNode=new Node(head.val);
        map.put(head,cloneNode);
        cloneNode.next=copyRandomList(head.next);
        cloneNode.random=copyRandomList(head.random);
        return cloneNode;
    }
}

Same idea as above using HashMap link-solution)

class Solution{
    public RandomListNode copyRandomList(RandomListNode head) {
        if (head == null) return null;
        
        Map<RandomListNode,RandomListNode> map = new HashMap<>();
        
        // loop 1. copy all the nodes
        RandomListNode node = head;
        while (node != null) {
            map.put(node, new RandomListNode(node.label));
            node = node.next;
        }
        
        // loop 2. assign next and random pointers
        node = head;
        while (node != null) {
            map.get(node).next = map.get(node.next);
            map.get(node).random = map.get(node.random);
            node = node.next;
        }
        
        return map.get(head);
    }
}

Time Complexity : O(N), Space Complexity : O(1) link

public class lc138 {
    public Node copyRandomList(Node head) {
        Node iter = head, next;
        // First round: make copy of each node,
        // and link them together side-by-side in a single list.
        while (iter != null) {
            next = iter.next;
            
            Node copy = new Node(iter.val);
            iter.next = copy;
            copy.next = next;

            iter = next;
        }

        // Second round: assign random pointers for the copy nodes.
        iter = head;
        while (iter != null) {
            if (iter.random != null) {
                iter.next.random = iter.random.next;
            }
            iter = iter.next.next;
        }

        // Third round: restore the original list, and extract the copy list.
        iter = head;
        Node pseudoHead = new Node(0);
        Node copy, copyIter = pseudoHead;
        while (iter != null) {
            next = iter.next.next;
            // extract the copy
            copy = iter.next;
            copyIter.next = copy;
            copyIter = copy;
            // restore the original list
            iter.next = next;
            iter = next;
        }
        return pseudoHead.next;
    }
}