复杂链表的复制Clone<TODO>

 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 */

 1 public class Solution {
 2     public RandomListNode Clone(RandomListNode pHead) {
 3         //考虑特殊情况
 4         if(pHead == null) {
 5             return null;
 6         }
 7         RandomListNode currentNode = pHead;
 8         //1、复制每个结点，如复制结点A得到A1，将结点A1插到结点A后面；
 9         //虽然过程有点绕,但是在纸上写一写还是能弄明白的
10         while(currentNode != null){
11             RandomListNode cloneNode = new RandomListNode(currentNode.label);
12             RandomListNode nextNode = currentNode.next;
13             currentNode.next = cloneNode;
14             cloneNode.next = nextNode;
15             currentNode = nextNode;
16         }
17         currentNode = pHead;
18         //2、重新遍历链表，复制老结点的随机指针给新结点，如A1.random = A.random.next;
19         while(currentNode != null) {
20             //? :语句先计算出来结果,然后赋值,比if else要强
21             currentNode.next.random = currentNode.random==null?null:currentNode.random.next;
22             currentNode = currentNode.next.next;
23         }
24         //3、拆分链表，将链表拆分为原链表和复制后的链表
25         currentNode = pHead;
26         //这个pCloneHead节点就是用来返回的,后期拆分操作肯定不会动头节点的
27         RandomListNode pCloneHead = pHead.next;
28         while(currentNode != null) {
29             RandomListNode cloneNode = currentNode.next;
30             currentNode.next = cloneNode.next;
31             cloneNode.next = cloneNode.next==null?null:cloneNode.next.next;
32             currentNode = currentNode.next;
33         }
34         return pCloneHead;
35     }
36 }