Problem

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

Example 1:

Input:
{"$id":"1","next":{"$id":"2","next":null,"random":{"$ref":"2"},"val":2},"random":{"$ref":"2"},"val":1}

Explanation:
Node 1's value is 1, both of its next and random pointer points to Node 2.
Node 2's value is 2, its next pointer points to null and its random pointer points to itself.

Note:

You must return the copy of the given head as a reference to the cloned list.

Explanation 1

In a normal linked list that each node has a next pointer, on top of it, this problem says each node also has a random pointer that points to other node in the linked list or null. We need to return a copy of this linked list.
First, we can create a new result node that has the same value as our input linked list’s head, and use a pointer resPtr pointing to it. Then starts from the second node using a pointer cur, use this pointer iterate the input linked list, and resPtr.next set to a new node that has the same value as the node that cur points at. This way, we can copy the normal linked list but not the random pointer. Also in each iteration, we can create a hashmap to map a cur pointer to its node because we don’t want to map result’s randome node to linked list’s random node res.random = cur.random, we want to map result’s random node to result’s node, not input linked list’s node res.random = randomResNode. (remember to map the first node because we start iterating from the second node map.put(head, res), key is the original linkedlist node, value is the result node).
After the first iteration, we got the copy of the normal linked list. Now we iterate this linked list again, to link the random pointer by using resPtr.random = map.get(curPtr);.

Solution 1

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return head;

        Node res = new Node(head.val);
        Node resPtr = res;
        Node cur = head.next;

        HashMap<Node, Node> map = new HashMap<>();
        map.put(head, res);

        while (cur != null) {
            Node temp = new Node(cur.val);
            resPtr.next = temp;
            map.put(cur, temp);
            resPtr = resPtr.next;
            cur = cur.next;
        }

        resPtr = res;
        cur = head;
        while (cur != null) {
            resPtr.random = map.get(cur.random);
            resPtr = resPtr.next;
            cur = cur.next;
        }

        return res;
    }
}

Explanation 2

In the above method, we used hashmap that costs extra space. This method can save space.
First, we copy a new node behind each node.
Then, we can assign new node’s random pointer by doing cur.next.random = cur.random.next.
Finally, we can cut off the original node and copied node’s list.

Solution 2

/*
// Definition for a Node.
class Node {
    public int val;
    public Node next;
    public Node random;

    public Node() {}

    public Node(int _val,Node _next,Node _random) {
        val = _val;
        next = _next;
        random = _random;
    }
};
*/
class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) return head;

        Node cur = head;
        while (cur != null) {
            Node temp = new Node(cur.val);
            temp.next = cur.next;
            cur.next = temp;
            cur = cur.next.next;
        }

        cur = head;
        while (cur != null) {
            if (cur.random != null) cur.next.random = cur.random.next;
            cur = cur.next.next;
        }

        cur = head;
        Node res = head.next;
        while (cur != null) {
            Node temp = cur.next;
            cur.next = temp.next;
            if (temp.next != null) temp.next = temp.next.next;
            cur = cur.next;
        }

        return res;
    }
}