题目

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.

大意

复制链表。

答案

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
class Solution {
public:
    RandomListNode *copyRandomList(RandomListNode *pHead) {
        if(!pHead) return NULL;
        RandomListNode* tou =pHead;
        RandomListNode* tou2=pHead;
        RandomListNode* tou3 =pHead;
        while(tou!=NULL)
        {
            RandomListNode* node =new RandomListNode(tou->label);
            node->random =NULL;
            RandomListNode* mynext =tou->next;
            tou->next =node;
            node->next =mynext;
            tou=tou->next->next;
        }
        while(tou2!=NULL)
        {
            RandomListNode* node =tou2->random;
            if(node)
            {
                tou2->next->random =node->next;
            }
            tou2=tou2->next->next;
        }
        RandomListNode *pCloneHead = pHead->next;
        RandomListNode *tmp;
        while(tou3->next)
        {
            tmp=tou3->next;
            tou3->next =tmp->next;
            tou3 =tmp;
        }
        return pCloneHead;
    }
};

思路

三步，第一步把每个结点插入原来结点的后面，第二步遍历去加上random指针，第三步要把两个彻底分开。（！！ ！ 第三步必须是把彻底分开两个链表，两个链表完全没重合，要不然通不过。）