138. Copy List with Random Pointer

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

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.

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) where random pointer points to, or null if it does not point to any node.

Example 1:

Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
Output: [[7,null],[13,0],[11,4],[10,2],[1,0]]

Example 2:

Input: head = [[1,1],[2,1]]
Output: [[1,1],[2,1]]

Example 3:

Input: head = [[3,null],[3,0],[3,null]]
Output: [[3,null],[3,0],[3,null]]

Example 4:

Input: head = []
Output: []
Explanation: Given linked list is empty (null pointer), so return null.

Constraints:

• -10000 <= Node.val <= 10000
• Node.random is null or pointing to a node in the linked list.
• Number of Nodes will not exceed 1000.

---

---
Space - O(1)

3 passes

1. Create cloned nodes, interleave with original
2. Connect random nodes on clones
3. Detach cloned list, and return its head

	/*
	// 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;
	}
	}
	*/
	class Solution {
	public Node copyRandomList(Node head) {
	if (head == null) {
	return null;
	}
	Node original = head;
	// insert clone nodes in between
	while (head != null) {
	Node clone = new Node(head.val);
	Node next = head.next;
	head.next = clone;
	clone.next = next;
	head = head.next.next;
	}
	// restart, connect random node on clone
	head = original;
	while (head != null) {
	Node clone = head.next;
	if (head.random != null) {
	clone.random = head.random.next;
	}
	// Advance two steps to next original node
	head = head.next.next;
	}
	// detach and return cloned list
	head = original;
	Node ans = original.next;
	while (head != null) {
	Node clone = head.next;
	head.next = head.next.next;
	if (head.next != null) {
	clone.next = head.next.next;
	}
	head = head.next;
	}
	return ans;
	}
	}

view raw 138.CopyListWithRandomPointerConstantSpace.java hosted with ❤ by GitHub

---
Space - O(N)

1 pass

1. Map original node to new
2. If original has random, attach random
3. If original has next, attach next

	/*
	// 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;
	}
	}
	*/
	class Solution {
	public Node copyRandomList(Node head) {
	Map<Node, Node> map = new HashMap<Node, Node>();
	Node copy = head;
	while (head != null) {
	Node clone = new Node(head.val);
	map.put(head, clone);
	head = head.next;
	}
	head = copy;
	while (head != null) {
	Node clone = map.get(head);
	if (head.next != null) {
	clone.next = map.get(head.next);
	}
	if (head.random != null) {
	clone.random = map.get(head.random);
	}
	head = head.next;
	}
	return map.get(copy);
	}
	}

view raw 138.CopyListWithRandomPointerExtraSpace.java hosted with ❤ by GitHub