Copy List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null. Return a deep copy of the list.
Solution:
- Add new node after each node
- Map the random pointer for each node to its corresponding new node
- Split the new nodes from the old linked list
Code:
/**
* Definition for singly-linked list with a random pointer.
* class RandomListNode {
* int label;
* RandomListNode next, random;
* RandomListNode(int x) { this.label = x; }
* };
*/
public class Solution {
/**
* @param head: The head of linked list with a random pointer.
* @return: A new head of a deep copy of the list.
*/
public RandomListNode copyRandomList(RandomListNode head) {
if (head == null) {
return head;
}
addNewNode(head);
mapRandomPointers(head);
RandomListNode res = splitCopy(head);
return res;
}
private void printList(RandomListNode head) {
while (head != null) {
System.out.print(head.label + "->");
head = head.next;
}
System.out.println("Null");
}
private void addNewNode(RandomListNode head) {
while (head != null) {
RandomListNode temp = head.next;
head.next = new RandomListNode(head.label);
head.next.next = temp;
head = temp;
}
}
//this function cannot be used independently.
private void mapRandomPointers(RandomListNode head) {
while (head != null) {
if (head.random != null) {
head.next.random = head.random.next;
}
head = head.next.next;
}
}
private RandomListNode splitCopy(RandomListNode head) {
RandomListNode dummy = new RandomListNode(0);
RandomListNode curt = dummy;
while (head != null) {
curt.next = head.next;
head.next = head.next.next;
head = head.next;
curt = curt.next;
}
return dummy.next;
}
}