关于reorder list 的总结

发信人: apprentice00 (数学学徒), 信区: JobHunting
标  题: 关于reorder list 的总结
发信站: BBS 未名空间站 (Sun May 18 16:37:26 2014, 美东)

我本来用递归方法 但是超时了 本身代码没错 就是慢 为什么慢 因为在每个递归函数
中有O（n）的操作 这样n次递归导致总体O（n平方）

如果坚持递归方法 需要返回调整好的list的尾节点的下一个节点 这个是从网友那里学
来的 其实这个过程有点tricky  为什么不简单返回 list的头节点或者尾节点 而要返
回尾节点的下一个节点呢？ 思路是这样的 尾节点经过调整已经不是原来的尾节点了
它指向的下一个已经不是原来的顺序 那为什么不返回头节点呢 ？ 头节点其实不需要
返回 每次用next找就可以了 而且每次拿到头节点也不好用 必须多次next找到尾节点
又超时了

网友的方法 我改编成了java的    后边也有返回尾节点的方法

但是很容易出错 如果面试 还是用循环而不是递归的方法 当然面试无法检查是不是超
时 所以用我最早的方法也可以吧

/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
   
    public void reorderList(ListNode head) {
       
        if(head == null)
        return;
       

        ListNode scanner = head;
        int length =0;
        while(scanner != null){
            length++;
            scanner = scanner.next;
        }
       
        reorderHelper(head, length);
       
       
    }
   
   
    // helper returns the very last node's next node
    public ListNode reorderHelper(ListNode start, int range){
          
 
          if(range ==0)
            return null;
         
          ListNode result = null;
           
        // range == 1 and range ==2 cases don't need adjustment   
          if(range ==1){
              result = start.next;
              start.next = null;
              return result;
          }
         
          if(range ==2){
              result = start.next.next;
              start.next.next = null;
              return result;
          }
   
         
          ListNode temp = reorderHelper(start.next, range -2);
         
          result = temp.next;
          temp.next = start.next;
          start.next = temp;
          
       
         return result;
    }
   
}



但是我想如果一定要返回尾节点如何 我也找到了答案 但是返回值仅仅用于存储其下一
个节点

/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
   
    public void reorderList(ListNode head) {
       
        if(head == null)
        return;
       

        ListNode scanner = head;
        int length =0;
        while(scanner != null){
            length++;
            scanner = scanner.next;
        }
       
        reorderHelper(head, length);
       
       
    }
   
   
    // helper returns the very last node's next node
    public ListNode reorderHelper(ListNode start, int range){
          
 
          if(range ==0)
            return null;
         
          ListNode result = null;
           
        // range == 1 and range ==2 cases don't need adjustment   
          if(range ==1){
              result = new ListNode(0);
              result.next = start.next;
              start.next = null;
              return result;
          }
         
          if(range ==2){
              result = new ListNode(0);
              result.next = start.next.next;
              start.next.next = null;
              return result;
          }
   
         
          ListNode temp = reorderHelper(start.next, range -2);
         
          result = new ListNode(0);
          result.next = temp.next.next;
          temp.next.next = start.next;
          start.next = temp.next;
          
       
         return result;
    }
   
}


--
※ 来源:·WWW 未名空间站 网址：mitbbs.com 移动：在应用商店搜索未名空间·[FROM: 107.]

http://www.mitbbs.com/article_t/JobHunting/32698901.html

FT中文十大 华尔街中文十大 水木十大 小百合十大 饮水思源十大 日月光华十大

京东618，图书音像满200立减100元 ， 更多京东优惠券