LeetCode OJ

参考了一个前辈的算法，能够在O(n)的时间复杂度，O(1)的空间复杂度内解决这个问题。算法过程如下图所示。总共有三个步骤：

下面是AC代码：

 1 class RandomListNode{
 2     int label;
 3     RandomListNode next, random;
 4     RandomListNode(int x){ this.label = x;}
 5 }
 6 
 7 /**
 8      * deep copy with random pointer
 9      * @param head
10      * @return
11      */
12     public RandomListNode copyRandomList(RandomListNode head){
13         if(head == null )
14             return null;
15         RandomListNode p = head;
16         do{
17             RandomListNode q = p.next;
18             p.next = new RandomListNode(p.label);
19             p.next.next = q;
20             p = q;
21         }while(p!=null);
22         
23         p = head;
24         do{
25             RandomListNode q = p.next.next;
26             p.next.random = p.random == null? null: p.random.next;
27             p = q;
28         }while(p!=null);
29         
30         p=head;
31         RandomListNode q = p.next;
32         RandomListNode ch = p.next;
33         RandomListNode r = ch;
34         while(true)
35         {
36             p.next = q.next;
37             r.next = q.next== null? null:q.next.next;
38             if(q.next==null)
39                 break;
40             q=r.next;
41             r = q;
42             p = p.next;
43         }
44             
45         return ch;
46     }

有问题可以和我联系，bettyting2010#163 dot com