复杂链表的复制（java）

问题描述

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

返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

题解

 1 /*
 2 public class RandomListNode {
 3     int label;
 4     RandomListNode next = null;
 5     RandomListNode random = null;
 6 
 7     RandomListNode(int label) {
 8         this.label = label;
 9     }
10 }
11 */
12 public class Solution {
13     public RandomListNode Clone(RandomListNode pHead)
14     {
15         cloneNodes(pHead);
16         cloneRandom(pHead);
17         return ReConnectNode(pHead);
18     }
19     
20     private void cloneNodes(RandomListNode pHead){
21         RandomListNode pNode=pHead;
22         while(pNode!=null){
23             RandomListNode randomListNode=new RandomListNode(pNode.label);
24             randomListNode.next=pNode.next;
25             pNode.next=randomListNode;
26             pNode=randomListNode.next;
27         }
28     }
29      
30     private void cloneRandom(RandomListNode pHead){
31         RandomListNode pNode=pHead;
32         while(pNode!=null){
33             System.out.println(pNode.label);
34             if(pNode.random!=null){
35                 pNode.next.random=pNode.random.next;
36             }else{
37                 pNode.next.random=null;
38             }
39             pNode=pNode.next.next;
40         }
41     }
42      
43     public static RandomListNode ReConnectNode(RandomListNode pHead){
44         RandomListNode node = pHead;
45         RandomListNode pCloneHead = null;
46         RandomListNode pCloneNode = null;
47         if(node!=null){
48             pCloneHead = pCloneNode = node.next;
49             node.next = pCloneHead.next;
50             node = node.next;
51         }
52         while(node!=null){
53             pCloneNode.next = node.next;
54             pCloneNode = pCloneNode.next;
55             node.next = pCloneNode.next;
56             node = node.next;
57         }
58         return pCloneHead;
59     }
60 }