輸入一個(gè)復(fù)雜鏈表（每個(gè)節(jié)點(diǎn)中有節(jié)點(diǎn)值蔽介，以及兩個(gè)指針伸头，一個(gè)指向下一個(gè)節(jié)點(diǎn)酪术，另一個(gè)特殊指針指向任意一個(gè)節(jié)點(diǎn)）阶剑。
返回一個(gè)該鏈表的深度拷貝.
思路:
- 遍歷該鏈表,復(fù)制每一個(gè)節(jié)點(diǎn),插入到當(dāng)前節(jié)點(diǎn)的后面.形成如下鏈表.
1->1'->2->2'.... - 將每個(gè)拷貝節(jié)點(diǎn)的隨機(jī)指針域,指向原節(jié)點(diǎn)(即拷貝節(jié)點(diǎn)的上一個(gè)節(jié)點(diǎn))的隨即指針域指向(注意隨機(jī)指針域可能為空)的下一個(gè)節(jié)點(diǎn).即1的隨機(jī)指針域指向3,則1'的隨機(jī)指針域指向3的下一個(gè)指針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;
}
}
