Vintion's blog

~夜黑路滑，社会复杂~

Leetcode-copy List With Random Pointer

| Comments

Copy List with random pointer

这题早就看过，解法也知道，但是，想法与代码差距很大，半天都没发现错误．还得多多练习

Problem

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.

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
49
50
51
52

/**
 * 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 *Head = head;
        if(NULL==head)
            return NULL;
        RandomListNode *p,*q;
        p = head;
        while(NULL!=p)
        {
            q = new RandomListNode(p->label);
            q->next = p->next;
            p->next = q;
            p = q->next;
        }
        p = head;
        while(NULL!=p)
        {
            if(p->random!=NULL) //　这里可能为空
                p->next->random = p->random->next;
            else
                p->next->random = NULL;
             p = p->next->next;
        }
        Head = head->next;
        p = head;
        q = Head;
        if(NULL==q->next)
        {
            p->next = NULL;
            return Head;
        }
        while(NULL!=q->next)
        {
            p->next =  q->next;
            p = p->next;
            q->next = p->next;
            q = q->next;
        }
       p->next = NULL;// 这里要断开
        return Head;
    }
};

两处注释的地方，瞪大眼睛都没看出来．

Comments