题目描述

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.

题目解析

其实这个题目跟剑指offer里面题目35复制复杂链表是一样的。我们以下图为例

所以这个题也是分为三步：

• 第一步：逐一复制A和B和C和D，复制后为A’、B’、C’和D’（加’是为了表示方便，实际上还是原来的值’），并把他们分别插入到原节点后面。
  代码如下：

  for(p=head;p;p=p->next){
      copy = new RandomListNode(p->label);
      copy->next = p->next; // insert new at old next
      p = p->next = copy;
  }

for循环中的p=head就实现了这样的功能：

for循环里面第一个语句就是新建一个节点（例如A’），第二行就是把这个A’的next指针指向B（因为原本A的next就是B的地址），然后把A’的地址赋值给p->next，也就是说head->的next是A’（即第三行里面的p->next=copy）。

然后的把p->next的地址给p，也就是把copy的地址（A’）给p，这个时候p又指向了A’。
然后判断p是否是空呢？不是，那么就把p移动到下一个节点，也就是B了。然后再同理进行操作，直到最后一个节点复制完成，退出循环。这个时候结果如下：

• 第二步：复制random结点。这一部分其实就是很简单，遍历A/B/C/D，然后判断这个节点（假设为X）的random指针有没有指向某个地方（也就是!nullptr），如果有的话就复制到相应的节点（A’）的random上。
  这部分也是很巧妙的利用了for循环的第三个参数和函数体里面的第一个语句实现了copy指向X’，p指向X（这里，假如此时p指向X,那么运行copy=p->next之后，copy指向了X，然后执行p=copy->next之后，p指向了（X+1），以此类推）。

for(p=head;p;p=copy->next){
    copy = p->next;          // copy random point
    copy->random = (p->random?p->random->next:NULL);
}

此时的结果为

• 第三步：断链。实现A->B->C->D，和A’->B’->C’->D’。先让p指向head，head是原本的ABCD那条链。因为我们要返回head，所以我们可以把head指向copy，然后操作copy即可。在for后面的第一个条件语句执行之后，p指向了A，copy和head指向了A’。然后下面自然就是进行断链操作了。断链结果如图所示。head指向的是copy，所以return head返回的就是图中下面的链。

代码实现

/**
 * 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 *copy,*p;
        if (!head) return NULL;
        for(p=head;p;p=p->next){
            copy = new RandomListNode(p->label);
            copy->next = p->next; // insert new at old next
            p = p->next = copy;
        }
        for(p=head;p;p=copy->next){
            copy = p->next;          // copy random point
            copy->random = (p->random?p->random->next:NULL);
        }
        for(p=head,head=copy=p->next;p;){
            p = p->next = copy->next; // split list
            copy = copy->next = (p?p->next:NULL);
        }
        return head;
    }
};