138. 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:

Method 1: use HashMap

1. Go through list, map each node with a deep copy of it (value only).
2. Go through list, for each node, add its copy's next pointer.
3. Go through list, for each node, add its copy's random pointer.

Time complexity is O(n).
Space complexity is O(n).



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 {
    public RandomListNode copyRandomList(RandomListNode head) {
        HashMap<RandomListNode, RandomListNode> map = new HashMap<>();
        RandomListNode curr = head;
        while (curr != null) {
            map.put(curr, new RandomListNode(curr.label));
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            map.get(curr).next = map.get(curr.next);
            curr = curr.next;
        }
        curr = head;
        while (curr != null) {
            map.get(curr).random = map.get(curr.random);
            curr = curr.next;
        }
        return map.get(head);
    }
}

Method 2: constant space

1. Go through list, for each node, add a deep copy (value only) between the node and its next node.
a -> b -> c  
=> a -> a' -> b -> b' -> c -> c'

2. Go through list, add deep copy's random pointer

3. Split.
a -> a' -> b -> b' -> c -> c'
=>
a -> b -> c
a' -> b' -> c'

Time complexity is O(n).
Space complexity is O(1).



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 {
    public RandomListNode copyRandomList(RandomListNode head) {
        RandomListNode curr = head;
        while (curr != null) {
            RandomListNode copy = new RandomListNode(curr.label);
            copy.next = curr.next;
            curr.next = copy;
            curr = copy.next;
        }
        curr = head;
        while (curr != null) {
            RandomListNode copy = curr.next;
            if (curr.random != null) {
                copy.random = curr.random.next;
            }
            curr = copy.next;
        }
        curr = head;
        RandomListNode dummy = new RandomListNode(0);
        RandomListNode currCopy = dummy;
        while (curr != null) {
            RandomListNode copy = curr.next;
            currCopy.next = copy;
            currCopy = copy;
            curr.next = copy.next;
            curr = copy.next;
        }
        return dummy.next;
    }
}