Clone a linked list with next and random pointer
???? Problem:
You are given a linked list where each node has a next pointer and a random pointer. The task is to clone the list such that both the next and random pointers of the new nodes point to the corresponding nodes in the copied list, with no reference to the original list.
?? Example:
?? Approach:
To solve this problem efficiently with O(n) time complexity and O(1) space complexity, we'll adopt a three-step approach:
领英推荐
?? Sample Code:
class Node {
int data;
Node next, random;
Node(int d) {
data = d;
next = random = null;
}
}
class Solution {
// Function to clone a linked list with next and random pointer.
Node copyList(Node head) {
if (head == null) return null;
// Step 1: Insert copy nodes
Node curr = head;
while (curr != null) {
Node newNode = new Node(curr.data);
newNode.next = curr.next;
curr.next = newNode;
curr = newNode.next;
}
// Step 2: Fix random pointers
curr = head;
while (curr != null) {
if (curr.random != null) {
curr.next.random = curr.random.next;
}
curr = curr.next.next;
}
// Step 3: Separate the lists
curr = head;
Node copyHead = head.next;
Node copy = copyHead;
while (curr != null) {
curr.next = curr.next.next;
if (copy.next != null) {
copy.next = copy.next.next;
}
curr = curr.next;
copy = copy.next;
}
return copyHead;
}
}
?? Time Complexity:
?? Summary:
Using a three-step approach (duplicating nodes, setting random pointers, and separating the lists), we achieve a cloned linked list in optimal time and space complexity. The beauty of this approach is its space efficiency, with O(1) extra space being used!