Problem description:

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:

  1. Copy the list within the original list

    original: A→B→C

    after: A→A’→B→B’→C→C’

  2. Copy the random pointer. Notice need to check if it’s None

  3. Separate two lists
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
"""
# Definition for a Node.
class Node:
    def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
        self.val = int(x)
        self.next = next
        self.random = random
"""

class Solution:
    def copyRandomList(self, head: 'Node') -> 'Node':
        if not head:
            return head
        
        p = head
        while p:
            newNode = Node(p.val)
            newNode.next = p.next
            p.next = newNode
            p = p.next.next
        p = head
        while p:
            if p.random:
                p.next.random = p.random.next
            p = p.next.next
            
        copy, p = head.next, head.next
        while p.next:
            head.next = p.next
            head = head.next
            p.next = head.next
            p = p.next
        head.next = None
        return copy

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
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *newHead, *l1, *l2;
        if (head == NULL) return NULL;
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            l2 = new RandomListNode(l1->label);
            l2->next = l1->next;
            l1->next = l2;
        }
        
        newHead = head->next;
        for (l1 = head; l1 != NULL; l1 = l1->next->next) {
            if (l1->random != NULL) l1->next->random = l1->random->next;
        }
        
        for (l1 = head; l1 != NULL; l1 = l1->next) {
            l2 = l1->next;
            l1->next = l2->next;
            if (l2->next != NULL) l2->next = l2->next->next;
        }
        return newHead;
    }
};

Second time:

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
39
40
/**
 * Definition for singly-linked list with a random pointer.
 * struct RandomListNode {
 *     int label;
 *     RandomListNode *next, *random;
 *     RandomListNode(int x) : label(x), next(NULL), random(NULL) {}
 * };
 */
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *head) {
        RandomListNode *newhead, *l1, *l2;
        if(!head) return NULL;
        l1= head;
        while(l1){
            l2= new RandomListNode(l1->label);
            l2->next= l1->next;
            l1->next= l2;
            l1= l1->next->next;
        }
        newhead= head->next;
        l1= head;
        l2= newhead;
        while(l1){
            if(l1->random)
                l1->next->random= l1->random->next;
            l1= l1->next->next;
        }
        
        l1= head;
        while(l1){
            l2= l1->next;
            l1->next= l2->next;
            if(l2->next)
                l2->next= l2->next->next;
            l1= l1->next;
        }
        return newhead;
    }
};

reference:
https://goo.gl/bq52sh
https://leetcode.com/problems/copy-list-with-random-pointer/discuss/43491/A-solution-with-constant-space-complexity-O(1)-and-linear-time-complexity-O(N)/42652