[LeetCode] Problem 138 - Copy List with Random Pointer

Posted on | In ,

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.

Example

k5eY34.png

Input:
{“$id”:”1”,”next”:{“$id”:”2”,”next”:null,”random”:{“$ref”:”2”},”val”:2},”random”:{“$ref”:”2”},”val”:1}

Explanation:
Node 1’s value is 1, both of its next and random pointer points to Node 2.
Node 2’s value is 2, its next pointer points to null and its random pointer points to itself.

Code

1
2
3
4
5
public class RandomListNode {
    int label;
    RandomListNode next, random;
    RandomListNode(int x) { this.label = x; }
 }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
// O(n) runtime, O(1) space – Modify original structure
public RandomListNode copyRandomList(RandomListNode head) {
    RandomListNode current = head;
    RandomListNode copyHead = null, copyCurrent = null;

    while (current != null) {
        RandomListNode copy = new RandomListNode(current.label);
        copy.next = current.next;
        current.next = copy;
        current = copy.next;
    }

    current = head;

    while (current != null) {
        if (current.random != null)
            current.next.random = current.random.next;

        current = current.next.next;
    }

    current = head;

    if (current != null) {
        copyHead = copyCurrent = current.next;
        current.next = current.next.next;
        current = copyCurrent.next;
    }

    while (current != null) {
        copyCurrent.next = current.next;
        current.next = current.next.next;
        copyCurrent = copyCurrent.next;
        current = current.next;
    }

    return copyHead;
}