Copying a linked list with random pointers is a classic problem in computer science and is commonly asked in technical interviews. In this article, we will explore how to solve this problem using Java like on hackernoon.com/java-algorithms-copying-list-with-random-pointer-leetcode.
The Problem Statement
The problem is as follows: You are given a linked list where each node has two pointers – a next pointer pointing to the next node in the list, and a random pointer pointing to a random node in the list. You need to make a deep copy of the original list.
This means that for each node in the original list, you should create a new node in the copied list with the same value, and the copied list’s next pointer should point to the copied next node, and the copied list’s random pointer should point to the copied random node.
Approach 1: Using a Hash Map
One way to solve this problem is by using a hash map to keep track of the mapping between nodes in the original list and nodes in the copied list. Here are the steps to do this:
- Create an empty hash map where the keys are nodes in the original list, and the values are nodes in the copied list.
- Iterate through the original list, and for each node, create a new node in the copied list with the same value.
- Put the mapping between the original node and the copied node into the hash map.
- Iterate through the original list again, and for each node, set the next pointer and random pointer of the copied node based on the mapping stored in the hash map.
// Java code to copy a linked list with random pointers
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
Map<Node, Node> map = new HashMap<>();
// First pass: create new nodes and map them
Node current = head;
while (current != null) {
map.put(current, new Node(current.val));
current = current.next;
}
// Second pass: assign next and random pointers
current = head;
while (current != null) {
Node newNode = map.get(current);
newNode.next = map.get(current.next);
newNode.random = map.get(current.random);
current = current.next;
}
return map.get(head);
}
This approach has a time complexity of O(N) where N is the number of nodes in the linked list, and a space complexity of O(N) due to the hash map.
Approach 2: Modifying the Original List
Another approach to solve this problem is by modifying the original list itself to create the copied list. Here are the steps:
- For each node in the original list, create a new node with the same value and insert it immediately after the original node.
- Iterate through the modified list, and for each node, set its random pointer to the node after its random pointer in the original list.
- Split the modified list into two separate lists – the original list and the copied list.
// Java code to copy a linked list with random pointers by modifying the original list
public Node copyRandomList(Node head) {
if (head == null) {
return null;
}
// Step 1: Duplicate each node and insert it after the original node
Node current = head;
while (current != null) {
Node copy = new Node(current.val);
copy.next = current.next;
current.next = copy;
current = copy.next;
}
// Step 2: Set 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;
}
// Step 3: Split the original list and the copied list
Node newHead = head.next;
Node p1 = head;
Node p2 = newHead;
while (p1 != null) {
p1.next = p2.next;
p1 = p1.next;
if (p1 != null) {
p2.next = p1.next;
p2 = p2.next;
}
}
return newHead;
}
This approach also has a time complexity of O(N) and a space complexity of O(1) since it modifies the original list in-place.
Conclusion
In this article, we discussed two approaches to copy a linked list with random pointers in Java. This problem is a great example of how data structures and algorithms are used to solve real-world problems, and it is a common topic in technical interviews. Understanding these concepts and practicing with similar problems can help you become a better programmer and excel in interviews.
External Links like hackernoon.com/java-algorithms-copying-list-with-random-pointer-leetcode.
- Hackernoon: A platform for tech enthusiasts and developers to share their knowledge and insights.
- Understanding PyTorch Transformations: A Guide to Reshaping Tensors: An informative article on reshaping tensors using PyTorch.
- The FindPeaks Function in MATLAB: Detecting Peaks in Data: Learn how to detect peaks in data using MATLAB.