Leetcode/138.CopyListwithRandomPointer.h at master · bluepp/Leetcode · 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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
/*
    bluepp
    2014-06-07
    2014-07-10
    2014-08-12
    May the force be with me!

    Problem:    Copy List with Random Pointer
    Source:     http://oj.leetcode.com/problems/copy-list-with-random-pointer/
    Notes:
    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: Solution 1 uses constant extra space.
*/

/* Solution 1 */

    RandomListNode *copyRandomList(RandomListNode *head) {

        RandomListNode *pCurr = head;
        while (pCurr)
        {
            RandomListNode *pNew = new RandomListNode(pCurr->label);
            pNew->next = pCurr->next;
            pCurr->next = pNew;
            pCurr = pCurr->next->next;
        }

        pCurr = head;
        while (pCurr)
        {
            if (pCurr->random) pCurr->next->random = pCurr->random->next;
            pCurr = pCurr->next->next;
        }

        RandomListNode dummy(0), *pNew = &dummy;
        pCurr = head;
        while (pCurr)
        {
            pNew->next = pCurr->next;
            pNew = pNew->next;
            pCurr->next = pCurr->next->next;
            pCurr = pCurr->next;
        }


        return dummy.next;

    }


/* Solution 2 */
    RandomListNode *copyRandomList(RandomListNode *head) {
        if (!head)
            return NULL;
        unordered_map<RandomListNode*, RandomListNode*> map;
        RandomListNode dummy(0), *pCurrNew = &dummy, *pCurr = head;

        while (pCurr)
        {
            if (map.find(pCurr) == map.end())
            {
                map[pCurr] = new RandomListNode(pCurr->label);
            }
            if (pCurr->random && map.find(pCurr->random) == map.end())
            {
                map[pCurr->random] = new RandomListNode(pCurr->random->label);
            }

            pCurrNew->next = map[pCurr];
            pCurrNew = pCurrNew->next;
            pCurrNew->random = map[pCurr->random];
            pCurr = pCurr->next;
        }

        return dummy.next;

    }