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. i.e. Return a deep copy of the list.

OR

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

Construct a deep copy of the list. The deep copy should consist of exactly n brand new nodes, where each new node has its value set to the value of its corresponding original node. Both the next and random pointer of the new nodes should point to new nodes in the copied list such that the pointers in the original list and copied list represent the same list state. None of the pointers in the new list should point to nodes in the original list.

For example, if there are two nodes X and Y in the original list, where X.random --> Y, then for the corresponding two nodes x and y in the copied list, x.random --> y.

Return the head of the copied linked list.

The linked list is represented in the input/output as a list of n nodes. Each node is represented as a pair of [val, random_index] where:

  • val: an integer representing Node.val
  • random_index: the index of the node (range from 0 to n-1) that the random pointer points to, or null if it does not point to any node.

Your code will only be given the head of the original linked list.

Examples

Example 1:

Input: head = [ [1,3],[2,1],[3,5],[4,3],[5,2] ]
Output: [ [1,3],[2,1],[3,5],[4,3],[5,2] ]

This is a random list node:

class RandomListNode {
	int val; //Node data
	Node next, random; //Next and random reference

	public Node(int data) {
		this.val = data;
		this.next = this.random = null;
	}
}

Solution

Method 1 - Using HashMap (Easier) - 2 Pass

We can use a HashMap which makes it simpler.

Code

Java

public RandomListNode copyRandomList(RandomListNode head) {
	if (head == null)
		return null;
	Map<RandomListNode, RandomListNode> old2CopyMap = new HashMap<> ();

	RandomListNode curr = head;
	// pass 1
	while (p != null) {
		RandomListNode copy = new RandomListNode(p.val);
		old2CopyMap.put(curr, copy);
		curr = curr.next;
	}

	curr = head;
	// pass 2
	while (curr != null) {
		RandomListNode copy = old2CopyMap.get(curr);
		copy.next = old2CopyMap(curr.next);
		copy.random = old2CopyMap(curr.random);
		curr = curr.next;
	}

	return old2CopyMap.get(head);
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(n)

Method 2 - Temporary List Modification - 3 Pass

To solve this problem, follow these steps as illustrated in the diagram below:

  1. Create a copy of each node and insert it immediately after the original node: copy.next = curr.next; curr.next = copy
  2. Assign the random pointers for all newly created nodes: curr.next.random = curr.random.next
  3. Split the list into two separate lists: newHead = curr.next curr.next=curr.next.next

Code

Java
public RandomListNode copyRandomList(RandomListNode head) {
	if (head == null) {
		return null;
	}

	// copy every node and insert to list
	RandomListNode curr = head;
	while (curr != null) {
		RandomListNode copy = new RandomListNode(curr.val);
		copy.next = curr.next;
		curr.next = copy;
		curr = copy.next;
	}

	// copy random pointer for each new node
	curr = head;
	while (curr != null) {
		if (curr.random != null) {
			curr.next.random = curr.random.next;
		} else {
			curr.next.random = null;
		}

		curr = curr.next.next;
	}

	
	// break list to two
	curr = head;
	RandomListNode newHead = head.next;
	RandomListNode copy = newHead;
	while (curr != null) {
		curr.next = curr.next.next;
		// as copy is on odd position, it may become null earler that curr pointer
		copy.next = copy.next != null ? copy.next.next: null;
		curr = curr.next;
		copy = copy.next;
	}

	return newHead;
}

Complexity

  • ⏰ Time complexity: O(n)
  • 🧺 Space complexity: O(1)