首页 > 代码库 > Copy List with Random Pointer leetcode java

Copy List with Random Pointer leetcode java

题目:

 

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.

Return a deep copy of the list.

 

题解:

如果要copy一个带有random pointer的list,主要的问题就是有可能这个random指向的位置还没有被copy到,所以解决方法都是多次扫描list。

 

第一种方法,就是使用HashMap来坐,HashMap的key存原始pointer,value存新的pointer。

第一遍,先不copy random的值,只copy数值建立好新的链表。并把新旧pointer存在HashMap中。

第二遍,遍历旧表,复制random的值,因为第一遍已经把链表复制好了并且也存在HashMap里了,所以只需从HashMap中,把当前旧的node.random作为key值,得到新的value的值,并把其赋给新node.random就好。

代码如下:

 

 1 public RandomListNode copyRandomList(RandomListNode head) {
 2         if(head==null)
 3             return null;
 4         HashMap<RandomListNode,RandomListNode> map = new HashMap<RandomListNode,RandomListNode>();
 5         RandomListNode newhead = new RandomListNode(head.label);
 6         map.put(head,newhead);
 7         RandomListNode oldp = head.next;
 8         RandomListNode newp = newhead;
 9         while(oldp!=null){
10             RandomListNode newnode = new RandomListNode(oldp.label);
11             map.put(oldp,newnode);
12             newp.next = newnode;
13             
14             oldp = oldp.next;
15             newp = newp.next;
16         }
17         
18         oldp = head;
19         newp = newhead;
20         while(oldp!=null){
21             newp.random = map.get(oldp.random);
22             oldp = oldp.next;
23             newp = newp.next;
24         }
25         
26         return newhead;
27     }

上面那种方法遍历2次list,所以时间复杂度是O(2n)=O(n),然后使用了HashMap,所以空间复杂度是O(n)。

 

 

第二种方法不使用HashMap来做,使空间复杂度降为O(1),不过需要3次遍历list,时间复杂度为O(3n)=O(n)。

 第一遍,对每个node进行复制,并插入其原始node的后面,新旧交替,变成重复链表。如:原始:1->2->3->null,复制后:1->1->2->2->3->3->null

 第二遍,遍历每个旧node,把旧node的random的复制给新node的random,因为链表已经是新旧交替的。所以复制方法为:

                                      node.next.random = node.random.next

             前面是说旧node的next的random,就是新node的random,后面是旧node的random的next,正好是新node,是从旧random复制来的。

 第三遍,则是把新旧两个表拆开,返回新的表即可。

 

代码如下:

 1  public RandomListNode copyRandomList(RandomListNode head) {
 2         if(head == null)  
 3             return head;  
 4         RandomListNode node = head;  
 5         while(node!=null){
 6             RandomListNode newNode = new RandomListNode(node.label);  
 7             newNode.next = node.next;  
 8             node.next = newNode;  
 9             node = newNode.next;  
10         } 
11         
12         node = head;  
13         while(node!=null){
14             if(node.random != null)  
15                 node.next.random = node.random.next;  
16             node = node.next.next;  
17         }
18         
19         RandomListNode newHead = head.next;  
20         node = head;  
21         while(node != null){  
22             RandomListNode newNode = node.next;  
23             node.next = newNode.next;  
24             if(newNode.next!=null)  
25                 newNode.next = newNode.next.next;  
26             node = node.next;  
27         }  
28         return newHead;  
29      }

 Reference:http://blog.csdn.net/linhuanmars/article/details/22463599