题目描述

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就实现了这样的功能:

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),以此类推)。

此时的结果为

  • 第三步:断链。实现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返回的就是图中下面的链。

代码实现