首页 > 代码库 > Leetcode Reorder List

Leetcode Reorder List

2024-08-03 11:04:35   221人阅读

Given a singly linked list L: L0→L1→…→Ln-1→Ln,
reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…

You must do this in-place without altering the nodes‘ values.

For example,
Given {1,2,3,4}, reorder it to {1,4,2,3}.

 

对于这道题我最开始是想的首先计算出链表总长度len，之后一个for循环，从0开始循环到len/2为止。内层循环维护左边链表一个索引和要插入的右边链表相对于左边链表的一个索引，然后再进行相应的删除插入操作。这样的时间代价为n2

后来发现运行时间超限制.

看网上有人说通过一个快指针和一个慢指针来查找链表中间节点，觉得这种查找中间节点的方法蛮好.以后遇到可以经常使用。

while（fast.next!=null&&fast.next.next!=null){}

之后将右半边的链表反转，这样只用一个循环即可同步操作。时间代价是线性的。

 

之后看网上有人提议用一个数组来维护链表各个节点的索引，一想这种方法很好，可以明确知道某个下标对应哪个节点。

代码如下：

 1 package ReorderList; 2  3 public class ReorderList1 { 4      public void reorderList(ListNode head) { 5          ListNode index=head; 6          int len=0; 7          while(index!=null){ 8          len++; 9          index=index.next;10          }11          ListNode [] array=new ListNode[len];12          index=head;13          for(int i=0;i<len;i++){14              array[i]=index;15              index=index.next;16          }17          index=head;18          for(int i=0;i<len/2;i++){19              ListNode insertObj=array[len-1-i];20              ListNode preInsertObj=array[len-1-i-1];21              preInsertObj.next=insertObj.next;22              ListNode currentObj=array[i];23              insertObj.next=currentObj.next;24              currentObj.next=insertObj;25          }26         }27 }

 

Leetcode Reorder List


联系
我们