Copy List with Random Pointer

Question (LC.138)

Given a speical linked list (each node contains a random pointer), make a deep copy of the list.

private class RandomListNode {
    int value;
    RandomListNode next;
    RandomListNode random;
    public RandomListNode(int value) {
        this.value = value;
    }
}

Example

For data structure questions, drawing out is normally a good idea since just thinking won't be very helpful.

Analysis

There are 4 types of edges - backward, forward, self, and null. Forward edges are troublesome because we don't know how far it will take us and thereby whether creating a new node.

BFS Approach

We can think of this question as a simplifying version of clone graph.

Step 1 Find all Vertices with BFS Explore
Step 2 Create a Deep Copy For Each Node
Step 3 Copy all Edges

Step 1 and Step 2 can be combined because next guarantees us the next node.

BFS Code

public RandomListNode copyRandomList(RandomListNode head) {
    if (head == null) return null;
    Map<RandomListNode, RandomListNode> orgClone = new HashMap<>();
    // Step 1 create a deep copy for each node
    RandomListNode travel = head;
    while (travel != null) {
        RandomListNode copy = new RandomListNode(travel.label);
        orgClone.put(travel, copy);
        travel = travel.next;
    }
    // Step 2 copy the random pointer
    for (RandomListNode org : orgClone.keySet()) {
        orgClone.get(org).next = orgClone.get(org.next);
        orgClone.get(org).random = orgClone.get(org.random);
    }
    return orgClone.get(head);
}

Even/Odd Approach

Step 1 Deep Copy Nodes and Store Adjacently
1->copy(1)->2->copy(2)->3->copy(3)->null

Step 2 Copy Random Pointers
travel.next.random = travel.random.next;
travel = travel.next.next;

Step 3 Restore the Original Extract the Copy
Set the next pointer
one travel pointer takes care of the copy list
another travel pointer takes care of the original list
save current.next.next as a temp pointer