剑指offer系列之二十四：复杂链表的复制

题目描述

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。

下面是我第一想到的思路：因为next指针是固定的，在复制的时候这点比较好处理，由于特殊指针是任意的，可能是在节点之前，也可能在节点之后，所以必须解决这个棘手问题。不管至少，可以从链表的第一个节点开始遍历，直到该特殊指针指向的节点，并设置该节点的特殊指针。还有一种思路（也是书上的思路）：第一步，复制原来链表的节点，并设置next指针，这一步不同于简单的复制节点，而是把每个复制的节点都链在原节点的后面，相当于复制节点之间隔了一个原节点；第二步，设置复制节点的特殊指针，由于在第一步左了特殊处理，所以当一个节点r的特殊指针指向节点n的时候，复制节点r’的特殊指针则是n’，这样就可以在o(1)时间定位到r的特殊指针指向的节点；第三步，从链表中抽取出复制节点，由于复制节点是间隔相连的，所以这一步比较好处理。综合以上三个步骤，就完成了复杂链表的复制。

下面是基于第二种思路的java代码（已被牛客ac）：