You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.
Create a deep copy of the list.
The deep copy should consist of exactly n new nodes, each including:
The original value val of the copied node
A next pointer to the new node corresponding to the next pointer of the original node
A random pointer to the new node corresponding to the random pointer of the original node
Note: None of the pointers in the new list should point to nodes in the original list.
Return the head of the copied linked list.
In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.
Example 1:
Input: head = [[3,null],[7,3],[4,0],[5,1]]
Output: [[3,null],[7,3],[4,0],[5,1]]
Example 2:
Input: head = [[1,null],[2,2],[3,2]]
Output: [[1,null],[2,2],[3,2]]
om the question we understand that we need to do a deep copy of every single node at-least to begin with?
Wat's the basic algorithm for deep copying linked list:
function deepCopy(head){
let dummy = new Node(0)
let newlist = dummy
let currentNode = head
while(currentNode){
let newNode = new Node(currentNode.val)
newlist.next = newNode
newlist = newlist.next
currentNode = currentNode.next
}
return dummy.next
}
we have a deep copy, just implementing this algorithm won't solve the problem. we also need to deal with the random pointer as well.
[1->2->3]
[1 -> 1' -> 2 -> 2' -> 3 -> 3']
Here, 1', 2', and 3' are the deep copies of 1, 2, and 3.
Step 1. Create a deep copy of every node
How??
function deepCopyNode(head){
let currentNode = head
while(currentNode){
let newNode = new Node(currentNode.val)
newNode.next = curretNode.next
currentNode.next = newNode
currentNode = newNode.next
}
}
Here we are assigining 1'.random -> 3'
the way to do is 1.next = 1'.random => 1.random = 3.next = 3'
1 is currentNode:
currentNode.next.random = currentNode.random.next
let currentNode = head // reseting back to head
while(currentNode){
if(currentNode.random){
currentNode.next.random = currentNode.random.next
}
}
Step 3: Separate the lists
1 -> 1' -> 2 -> 2'
#
0 -> 1'
let currentNode = head
let dummyNode = new Node(0)
let newList = dummyNode
while(currentNode){
// Move forward in the copied list
let newNode = currentNode.next
// Append the copied node to the copied list
newList.next = newNode
// Move forward in the copied list
newList = newNode
currentNode.next = newNode.next
}
The idea is to create a var of let newNode = new Node(currentNode.val)
which makes the code more simply than not defining it.
You are given the head of a linked list of length n. Unlike a singly linked list, each node contains an additional pointer random, which may point to any node in the list, or null.
Create a deep copy of the list.
The deep copy should consist of exactly n new nodes, each including:
Note: None of the pointers in the new list should point to nodes in the original list.
Return the head of the copied linked list.
In the examples, the linked list is represented as a list of n nodes. Each node is represented as a pair of [val, random_index] where random_index is the index of the node (0-indexed) that the random pointer points to, or null if it does not point to any node.
Example 1:
om the question we understand that we need to do a deep copy of every single node at-least to begin with?
Wat's the basic algorithm for deep copying linked list:
function deepCopy(head){ let dummy = new Node(0) let newlist = dummy let currentNode = head while(currentNode){ let newNode = new Node(currentNode.val) newlist.next = newNode newlist = newlist.next currentNode = currentNode.next } return dummy.next }we have a deep copy, just implementing this algorithm won't solve the problem. we also need to deal with the random pointer as well.
Step 1. Create a deep copy of every node
How??
function deepCopyNode(head){ let currentNode = head while(currentNode){ let newNode = new Node(currentNode.val) newNode.next = curretNode.next currentNode.next = newNode currentNode = newNode.next } }Step2: Assign random pointers
let currentNode = head // reseting back to head while(currentNode){ if(currentNode.random){ currentNode.next.random = currentNode.random.next } }Step 3: Separate the lists
1 -> 1' -> 2 -> 2' # 0 -> 1' let currentNode = head let dummyNode = new Node(0) let newList = dummyNode while(currentNode){ // Move forward in the copied list let newNode = currentNode.next // Append the copied node to the copied list newList.next = newNode // Move forward in the copied list newList = newNode currentNode.next = newNode.next }The idea is to create a var of let newNode = new Node(currentNode.val)
which makes the code more simply than not defining it.