Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
LinkedList - Deep copy
package com.interviewbytes.linkedlists;
import java.util.HashMap;
import java.util.Map;
public class CopyRandomList {
public RandomListNode copyRandomList(RandomListNode head) {
Map<RandomListNode, RandomListNode> mapping = new HashMap<>();
RandomListNode current = head;
while (current != null) {
if (!mapping.containsKey(current)) {
mapping.put(current, new RandomListNode(current.label));
}
current = current.next;
}
RandomListNode sentinel = new RandomListNode(0);
current = sentinel;
while (head != null) {
current.next = mapping.get(head);
current = current.next;
current.next = mapping.get(head.next);
current.random = mapping.get(head.random);
head = head.next;
}
return sentinel.next;
}
}
package com.interviewbytes.linkedlists;
public class RandomListNode {
int label;
RandomListNode next, random;
RandomListNode(int x) {
this.label = x;
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.