题目描述
输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
分析
常规的复制链表只需要考虑每个节点的next指针即可，但是该题还有另外一个random指针，且没有规律，可能指向任何其他节点，此时需要解决的问题是如何复制random指针。开始想先通过next指针构建新的链表，同时使用栈保存各个新节点，然后再通过栈来构建random指针，但是发现过程中并没有这么简单，比如对于A.random=C来说，那么在新链表中就是A1.random=C1，我无法在新链表中以O(1)的时间复杂度访问C1，所以我这种方法受阻。
在网上查到一种思路，遍历链表的时候把每个新节点添加在旧节点的后面，比如 A->B->C，复制完是A->A1->B->B1->C->C1，然后对于每个复制节点来说来说，A1.random=A.random.next，B1.random=B.random.next，C1.random=C.random.next，完美的解决了复制random指针时获取到目标节点的问题。最后再拆成两条链表即可。
代码实现
/*function RandomListNode(x){ this.label = x; this.next = null; this.random = null; }*/ function Clone(h) { if(h === null) return h; var cur = h; // 第一次遍历，先复制所有节点，且把复制节点添加到相应节点后面 while(cur !== null) { var node = new RandomListNode(cur.label); node.next = cur.next; cur.next = node; cur = node.next; } cur = h; // 第二次遍历，复制random指针 while(cur !== null) { if(cur.random !== null){ cur.next.random = cur.random.next; } cur = cur.next.next; } var clonedH = h.next; var temp; cur = h; // 第三次遍历，把链表拆开 while(cur.next !== null) { temp = cur.next; cur.next = cur.next.next; cur = temp; } return clonedH; }
