700186. Clone List with Next and Random
Clone List with Next and Random
Summary
Given a linked list where each node has three pointers, next, random and val, we need to clone this linked list. The next pointer points to the next node in the sequence, while the random pointer points to any other node (including itself) in the sequence. We need to create a new copy of this linked list.
Detailed Explanation
The key concept involved here is manipulation of pointers and nodes in a linked list.
To solve this problem, we will use a recursive approach. First, we will clone each node in the original list. Then, we will update the random pointer for each node to point to its corresponding copy.
Here's a step-by-step breakdown of the solution:
- Create a new node with the same value as the current node.
- Update the
nextpointer of the cloned node to point to the next clone in the sequence. - Update the
randompointer of the cloned node to point to its corresponding copy.
Here's an ASCII art diagram representing the original list and its clone:
Original List: A -> B -> C
Clone List: A' -> B' -> C'
Time complexity for this solution is O(N), where N is the number of nodes in the linked list. This is because we are visiting each node once.
Space complexity for this solution is also O(N), as we need to create a new copy of the entire list.
Optimized Solutions
Java
public Node cloneList(Node head) {
if (head == null) {
return null;
}
Node clone = new Node(head.val);
Node current = head.next;
Node original = head;
while (current != null) {
Node nextOriginal = current.next;
Node nextClone = new Node(current.val);
current.next = nextClone;
nextClone.next = nextOriginal;
current = nextOriginal;
}
current = head;
while (current != null) {
Node cloneNode = current.next;
current.next = cloneNode.next;
cloneNode.next = (current.random == null) ? null : ((NodeList)clone).get(cloneNode.random.index);
current = current.next;
}
return clone;
}