首页 > 代码库 > Leetcode Copy List with Random Pointer

Leetcode Copy List with Random Pointer

2024-08-03 23:39:04   212人阅读

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


联系
我们