输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点）。
返回一个该链表的深度拷贝.
思路:
- 遍历该链表,复制每一个节点,插入到当前节点的后面.形成如下链表.
1->1'->2->2'.... - 将每个拷贝节点的随机指针域,指向原节点(即拷贝节点的上一个节点)的随即指针域指向(注意随机指针域可能为空)的下一个节点.即1的随机指针域指向3,则1'的随机指针域指向3的下一个指针3'.
- 拆分链表,返回1'->2'->3'...
代码如下:
/*
public class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;
RandomListNode(int label) {
this.label = label;
}
}
*/
public class Solution {
public RandomListNode Clone(RandomListNode pHead)
{
if(pHead==null)return null;
RandomListNode runner=pHead;
RandomListNode copyCat=null;
//First round: make copy of each nodes
while(runner!=null){
copyCat=new RandomListNode(runner.label);
copyCat.next=runner.next;
runner.next=copyCat;
runner=copyCat.next;
}
//Second Round: assign random pointers for the copy nodes
runner=pHead;
while(runner!=null){
copyCat=runner.next;
//notice random pointers could be null
copyCat.random=runner.random==null?null:runner.random.next;
runner=runner.next.next;
}
//Third round: restore the original list, and extract the copy list.
runner=pHead;
pHead=runner.next;
while(true){
copyCat=runner.next;
runner.next=copyCat.next;
runner=copyCat.next;
if(runner==null){
break;
}
else{
copyCat.next=runner.next;
}
}
return pHead;
}
}
