首页 > 代码库 > Leetcode Reorder List
Leetcode Reorder List
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
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。