Algorithm

LintCode/Copy List With Random Pointer

Problem Summary

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

First, we make a copy of each node and insert it right after the original node.

Then, we need to find the “random” pointers for the new nodes.
Suppose we have a node p, whose random pointer points to node q, i.e. p->random == q. And after the copying, we have p->next == p2, q->next == q2. Then the random pointer of q1 should be q2. So we let p->next->random = p->random->next.

Finally, we break the linked list into two lists, the original one and the copy of it.

The time complexity is O(N), where N is the length of the linked list.

Code

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
41
42
43
44
45
46
47
48
/**
 * 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:
    /**
     * @param head: The head of linked list with a random pointer.
     * @return: A new head of a deep copy of the list.
     */
    RandomListNode *copyRandomList(RandomListNode *head) {
    	if (head == NULL)
    		return NULL;
        RandomListNode *p = head,*tmp;
        while (p)
        {
        	tmp = p->next;
        	p->next = new RandomListNode(p->label);
        	p->next->next = tmp;
        	p = p->next->next;
        }
        
        p = head;
        while (p)
        {
     		if (p->random == NULL)
     			p->next->random = NULL;
     		else
        		p->next->random = p->random->next;
        	p = p->next->next;
        }
        RandomListNode *res = head->next;
        p = head;
        while (p && p->next)
        {
            tmp = p->next;
            p->next = p->next->next;
            p = tmp;
        }
        
        return res;
    }
};