Clone Singly Linked List with data, next and random pointer (points to a random node of list)

We can use a hash table to associate newly created nodes with the instance of node in the given list.

i.e.
- Scan the original list and for each node X create an new node Y with data of X, then store the pair (X,Y) in hash table using X as a key.
- Noe, for each node X in original list we have a copy Y stored in our hash table. We scan again the original list and set the pointers buildings the new list.

ListNode Clone (ListNode head) {
    ListNode X = head, Y;
    Map HT = new HashMap();
    while(X != null){
        Y = new ListNode();
        Y.setData(X.getData());
        Y.setNext(null);
        Y.setRandom(null);
        HT.put(X, Y);
        X = X.getNext();
    }
    X = head;
    while(X != null) {
        //Get the node Y corresponding to Y from hash table
        Y = HT.get(X);
        Y.setNext(HT.get(X.getNext());
        Y.setRandom(HT.get(X.getRandom());
        X = X.getNext();
    }
    // Return the head of the new list, that is the node Y
    return HT.getNext(head);
}

Time Complexity: O(n). Space Complexity: O(n).