Description
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 representingNode.valrandom_index: the index of the node (range from0ton-1) that therandompointer points to, ornullif 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 = [[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]]Solution in Python
To solve the problem of making a deep copy of a linked list where each node contains an additional random pointer, we can use a two-pass algorithm. Here are the detailed steps:
Approach:
- First Pass – Create a Copy of Each Node:
- Traverse the original list and create a new node for each original node.
- Insert the newly created node right after the original node. This way, the copied node follows its corresponding original node directly in the list.
- Second Pass – Set Up the Random Pointers:
- Traverse the list again. For each original node, set the random pointer of the copied node to the copied version of the original node’s random pointer.
- Third Pass – Separate the Two Lists:
- Finally, restore the original list and extract the copied list.
# Definition for a Node.
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Optional[Node]') -> 'Optional[Node]':
if not head:
return None
# First pass: Create a copy of each node and insert it right after the original node.
current = head
while current:
new_node = Node(current.val, current.next, None)
current.next = new_node
current = new_node.next
# Second pass: Assign random pointers for the copied nodes.
current = head
while current:
if current.random:
current.next.random = current.random.next
current = current.next.next
# Third pass: Restore the original list and extract the copied list.
current = head
copy_head = head.next
while current:
copy = current.next
current.next = copy.next
if copy.next:
copy.next = copy.next.next
current = current.next
return copy_headExplanation:
- First Pass:
- For each node in the original list, create a new node with the same value.
- Insert this new node immediately after the original node.
- After this step, the list will look like:
original1 -> copy1 -> original2 -> copy2 -> ...
- Second Pass:
- Set the
randompointer of each copied node. - If an original node’s random pointer is not null, set the copied node’s random pointer to the copied version of the original node’s random node.
- This is done using
current.next.random = current.random.next.
- Set the
- Third Pass:
- Separate the original and copied nodes to restore the original list.
- Extract the copied nodes to form the new copied list.
- This is done by adjusting the
nextpointers appropriately.
This approach ensures that we maintain linear runtime complexity O(n) and use only constant extra space (not considering the space for the output).
Solution in Javascript
/**
* @param {_Node} head
* @return {_Node}
*/
var copyRandomList = function(head) {
if (!head) return null;
// First pass: Create a copy of each node and insert it right after the original node
let current = head;
while (current) {
let newNode = new _Node(current.val, current.next, null);
current.next = newNode;
current = newNode.next;
}
// Second pass: Assign random pointers for the copied nodes
current = head;
while (current) {
if (current.random) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: Restore the original list and extract the copied list
current = head;
let copyHead = head.next;
while (current) {
let copy = current.next;
current.next = copy.next;
if (copy.next) {
copy.next = copy.next.next;
}
current = current.next;
}
return copyHead;
};Solution in Java
class Solution {
public Node copyRandomList(Node head) {
if (head == null) return null;
// First pass: Create a copy of each node and insert it right after the original node
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// Second pass: Assign random pointers for the copied nodes
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: Restore the original list and extract the copied list
current = head;
Node copyHead = head.next;
while (current != null) {
Node copy = current.next;
current.next = copy.next;
if (copy.next != null) {
copy.next = copy.next.next;
}
current = current.next;
}
return copyHead;
}
}Solution in C#
public class Solution {
public Node CopyRandomList(Node head) {
if (head == null) return null;
// First pass: Create a copy of each node and insert it right after the original node
Node current = head;
while (current != null) {
Node newNode = new Node(current.val);
newNode.next = current.next;
current.next = newNode;
current = newNode.next;
}
// Second pass: Assign random pointers for the copied nodes
current = head;
while (current != null) {
if (current.random != null) {
current.next.random = current.random.next;
}
current = current.next.next;
}
// Third pass: Restore the original list and extract the copied list
current = head;
Node copyHead = head.next;
while (current != null) {
Node copy = current.next;
current.next = copy.next;
if (copy.next != null) {
copy.next = copy.next.next;
}
current = current.next;
}
return copyHead;
}
}