首页 > 代码库 > Leetcode Copy List with Random Pointer
Leetcode Copy List with Random Pointer
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.
对于这道题最开始用的是用一个数组存储新建的节点,然后对random的索引时比较快。
后来在网上看到人家的一种很奇特的方法,觉得也很好。
1.首先复制每一个节点,并把它插入到该节点的直接后继,这样就构成了一个新链表,链表长度为原来的二倍,同时每个节点有两个复制。
2.之后修改random域,new1->random = old1->random->next
3.将链表拆分成两个,old1->next = old1->next->next, new1->next = new1->next->next
此时的时间复杂度为O(n)
1 package Copy.List.with.Random.Pointer; 2 3 public class ListRandomPointer1 { 4 public RandomListNode copyRandomList(RandomListNode head) { 5 RandomListNode index=head; 6 if(head==null) return null; 7 while(index!=null){ 8 RandomListNode node=new RandomListNode(index.label); 9 RandomListNode temp=index.next; 10 node.next=temp;11 index.next=node;12 index=temp;13 }14 index=head;15 while(index!=null){16 if(index.random==null){17 index.next.random=null;18 }else{19 index.next.random=index.random.next;20 }21 index=index.next.next;22 }23 index=head;24 RandomListNode head2=head.next;25 RandomListNode index2=head2;26 while(index!=null){27 index.next=index2.next;28 if(index2.next!=null)29 index2.next=index2.next.next;30 index=index.next;31 if (index != null) { 32 index2 = index.next; 33 } 34 }35 return head2;36 }37 38 39 }
Leetcode Copy List with Random Pointer
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。