coding_solutions/copy_list_with_random_pointer.cpp at master · rs1820/coding_solutions · GitHub

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
/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* next;
    Node* random;

    Node(int _val) {
        val = _val;
        next = NULL;
        random = NULL;
    }
};
*/

class Solution {
public:
    Node* copyRandomList(Node* head) {
        Node* temp=head;
        while(temp){
            Node* next=temp->next;
            temp->next=new Node(temp->val);
            temp->next->next=next;
            temp=next;
        }
        temp=head;
        while(temp){
            temp->next->random=temp->random?temp->random->next:temp->random;
            temp=temp->next?temp->next->next:temp->next;
        }
        Node* original=head;
        Node* copy =head->next;
        temp=head->next;
        while(original && copy){
            original->next=original->next?original->next->next:original->next;
            copy->next=copy->next?copy->next->next:copy->next;
            original=original->next;
            copy=copy->next;
        }
        return temp;

    }
};