leetcode sortList

Sort a linked list in O(n log n) time using constant space complexity.
/**
* Definition for singly-linked list.
* class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
class ListNode{
    int val;
    ListNode next;
    ListNode(int x){
        val = x;
        next = null;
    }
}
public class Solution {
    public ListNode sortList(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        if(head == null){
            return null;
        }
        
        ListNode pre = head;
        while(slow.next!=null && fast.next!=null && fast!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode res = mergesort(head,slow);
        return res;
    }
   
    public ListNode mergesort(ListNode l1, ListNode l2){
        if(l2 == null || l1 == l2){
            return l1;
        }
        if(l1 == null){
            return l2;
        }
        ListNode slow = l1;
        ListNode fast = l1;
        ListNode pre = l1;
        while(slow.next!=null && fast.next!=null && fast!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode head1 = mergesort(l1,slow);
        slow = l2;
        fast = l2;
        pre = l2;
        while(slow.next!=null && fast.next!=null && fast!=null){
            pre = slow;
            slow = slow.next;
            fast = fast.next.next;
        }
        pre.next = null;
        ListNode head2 = mergesort(l2,slow);
        ListNode res = new ListNode(0);
        ListNode cur = res;
        while(head1!=null && head2 != null){
            if(head1.val<head2.val){
                cur.next = head1;
                head1 = head1.next;
            }
            else{
                cur.next = head2;
                head2 = head2.next;
            }
            cur = cur.next;
        }
        while(head1!=null){
            cur.next = head1;
            cur = cur.next;
            head1 = head1.next;
        }
        while(head2!=null){
            cur.next = head2;
            cur = cur.next;
            head2 = head2.next;
        }
        return res.next;
    }
}
显示是runtime error, executed input为{}，可是我对于head == null的情形已经有return null的指令了呀……求助

楼主, 我建议你先看下答案, 你上来自己写会导致错误的思维方式. 每个题都是有套路的. 都能归约成一系列问题.
你的code很散乱, 表示你不能把一道题归约到一类题...建议还是先从基础抓起

直接参考我的代码吧，  quick sort和merge sort都写了， 看注释。
你的代码太乱，不值得去花时间找bug。

1. /**
   
2. * Definition for singly-linked list.
   
3. * class ListNode {
   
4. *     int val;
   
5. *     ListNode next;
   
6. *     ListNode(int x) {
   
7. *         val = x;
   
8. *         next = null;
   
9. *     }
   
10. * }
    
11. */
    
12. public class Solution {
    
13.     //quick sort
    
14.     public ListNode sortList(ListNode head) {
    
15.         if (head == null || head.next == null) return head;
    
16.         int pivot = head.val;
    
17.         ListNode h1 = new ListNode(-1);
    
18.         ListNode hp = new ListNode(-1);
    
19.         ListNode h2 = new ListNode(-1);
    
20.         ListNode cur1 = h1;
    
21.         ListNode curp = hp;
    
22.         ListNode cur2 = h2;
    
23.         ListNode cur = head;
    
24.         while (cur != null) {
    
25.             if (cur.val < pivot) {
    
26.                 cur1.next = cur;
    
27.                 cur1 = cur1.next;
    
28.             } else if (cur.val > pivot) {
    
29.                 cur2.next = cur;
    
30.                 cur2 = cur2.next;
    
31.             } else {
    
32.                 curp.next = cur;
    
33.                 curp = curp.next;
    
34.             }
    
35.             cur = cur.next;
    
36.         }
    
37.         cur1.next = null;
    
38.         curp.next = null;
    
39.         cur2.next = null;
    
40.         
    
41.         return append(append(sortList(h1.next), hp.next), sortList(h2.next));
    
42.     }
    
43.    
    
44.     private ListNode append(ListNode h1, ListNode h2) {
    
45.         if (h1 == null) return h2;
    
46.         if (h2 == null) return h1;
    
47.         
    
48.         ListNode cur = h1;
    
49.         while (cur.next != null) cur = cur.next;
    
50.         cur.next = h2;
    
51.         
    
52.         return h1;
    
53.     }
    
54. 
    
55. /* merge sort
    
56.     public ListNode sortList(ListNode head) {
    
57.         if (head == null || head.next == null) return head;
    
58.         ListNode dummy = new ListNode(-1);
    
59.         dummy.next = head;
    
60.         ListNode h1 = dummy;
    
61.         ListNode h2 = dummy;
    
62.         
    
63.         while (h2 != null && h2.next != null) {
    
64.             h1 = h1.next;
    
65.             h2 = h2.next.next;
    
66.         }
    
67.         
    
68.         h2 = h1.next;
    
69.         h1.next = null;
    
70.         h1 = head;
    
71.         
    
72.         return merge(sortList(h1), sortList(h2));
    
73.     }
    
74.    
    
75.     private ListNode merge(ListNode l1, ListNode l2) {
    
76.         if (l1 == null) return l2;
    
77.         if (l2 == null) return l1;
    
78.         ListNode result = new ListNode(-1);
    
79.         ListNode curNode = result;
    
80.         while (l1 != null && l2 != null) {
    
81.             if (l1.val > l2.val) {
    
82.                 curNode.next = l2;
    
83.                 l2 = l2.next;
    
84.             } else {
    
85.                 curNode.next = l1;
    
86.                 l1 = l1.next;
    
87.             }
    
88.             curNode = curNode.next;
    
89.         }
    
90.         
    
91.         if (l1 != null) curNode.next = l1;
    
92.         if (l2 != null) curNode.next = l2;
    
93.         
    
94.         return result.next;
    
95.     }
    
96. */
    
97. }

复制代码

Kimurate 发表于 2014-8-2 12:11
我就是说实现很tricky……思想当然简单……

我仔细读了一下这个非递归的版本， 直觉上这个版本的代价是基于一些常数时间复杂度代价的（最里层1 - interval的循环）， 还有一些不好计算overhead。 为了验证猜测我提交测了一下， 比我的递归版本要慢了100+ 毫秒。

0 minutes ago        Accepted        472 ms        java
1 minute ago        Accepted        580 ms        java

一般来说递归进栈出栈需要的时间代价更大，空间复杂度logn更高那么对内存的开辟消耗也更多， 所以非递归版本速度一般是要高于递归版本，但是这个例子中为了实现理论上O(1)的空间而导致速度上反而不如，感觉失去了初衷。不知道还有更好或者更简洁的非递归实现版本没有， 我猜用一个(head, end)的二元组数据结构表示链表会有更好的效果。

先把代码贴贴好吧，你这里好多重复内容，确定你就这么写的吗。。。 另外用一下代码标签格式化，看上去也清楚很多。。。
看了下貌似真的是你原来的代码，不过推荐还是先多看看别人的代码，思考一下怎么精炼自己的；你现在这样就使劲练习的话，让我想起当时考GRE一个新东方作文老师说的，最后会把错误的表达方式练得炉火纯青了

ilnlh 发表于 2014-7-31 11:52
先把代码贴贴好吧，你这里好多重复内容，确定你就这么写的吗。。。 另外用一下代码标签格式化，看上去也清 ...

我确实很想要一份leetcode的参考答案，但一直都找不到……这边有链接么

readman 发表于 2014-7-31 11:58
楼主, 我建议你先看下答案, 你上来自己写会导致错误的思维方式. 每个题都是有套路的. 都能归约成一系列问题 ...

同上
顺便其实这已经是我参考别人的答案了，就是最普通的mergesort而已

北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧，  quick sort和merge sort都写了， 看注释。
你的代码太乱，不值得去花时间找bug。

你的解法和我的完全一样，惟一的区别就是你是复制了代码

北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧，  quick sort和merge sort都写了， 看注释。
你的代码太乱，不值得去花时间找bug。

顺便能问问是怎么复制代码的么

donnice 发表于 2014-7-31 14:40
顺便能问问是怎么复制代码的么

leetcode答案：https://github.com/soulmachine/leetcode

github是个好东西，嗯

weixc1234 发表于 2014-7-31 15:23
leetcode答案：https://github.com/soulmachine/leetcode

github是个好东西，嗯

诶，貌似只找到了C++的版本……