一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2637|回复: 30
收起左侧

[二分/排序/搜索] leetcode sortList

[复制链接] |试试Instant~ |关注本帖
donnice 发表于 2014-7-29 17:30:56 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
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的指令了呀……求助
readman 发表于 2014-7-31 11:58:17 | 显示全部楼层
楼主, 我建议你先看下答案, 你上来自己写会导致错误的思维方式. 每个题都是有套路的. 都能归约成一系列问题.
你的code很散乱, 表示你不能把一道题归约到一类题...建议还是先从基础抓起

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

ilnlh 发表于 2014-7-31 11:52:12 | 显示全部楼层
本帖最后由 ilnlh 于 2014-7-30 19:56 编辑

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

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

北美农民 发表于 2014-7-31 12:12:16 | 显示全部楼层
直接参考我的代码吧,  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. /* merge sort
  55.     public ListNode sortList(ListNode head) {
  56.         if (head == null || head.next == null) return head;
  57.         ListNode dummy = new ListNode(-1);
  58.         dummy.next = head;
  59.         ListNode h1 = dummy;
  60.         ListNode h2 = dummy;
  61.         
  62.         while (h2 != null && h2.next != null) {
  63.             h1 = h1.next;
  64.             h2 = h2.next.next;
  65.         }
  66.         
  67.         h2 = h1.next;
  68.         h1.next = null;
  69.         h1 = head;
  70.         
  71.         return merge(sortList(h1), sortList(h2));
  72.     }
  73.    
  74.     private ListNode merge(ListNode l1, ListNode l2) {
  75.         if (l1 == null) return l2;
  76.         if (l2 == null) return l1;
  77.         ListNode result = new ListNode(-1);
  78.         ListNode curNode = result;
  79.         while (l1 != null && l2 != null) {
  80.             if (l1.val > l2.val) {
  81.                 curNode.next = l2;
  82.                 l2 = l2.next;
  83.             } else {
  84.                 curNode.next = l1;
  85.                 l1 = l1.next;
  86.             }
  87.             curNode = curNode.next;
  88.         }
  89.         
  90.         if (l1 != null) curNode.next = l1;
  91.         if (l2 != null) curNode.next = l2;
  92.         
  93.         return result.next;
  94.     }
  95. */
  96. }
复制代码

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-7-31 14:37:16 | 显示全部楼层
ilnlh 发表于 2014-7-31 11:52
先把代码贴贴好吧,你这里好多重复内容,确定你就这么写的吗。。。 另外用一下代码标签格式化,看上去也清 ...

我确实很想要一份leetcode的参考答案,但一直都找不到……这边有链接么
回复 支持 反对

使用道具 举报

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

同上
顺便其实这已经是我参考别人的答案了,就是最普通的mergesort而已
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-7-31 14:38:54 | 显示全部楼层
北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧,  quick sort和merge sort都写了, 看注释。
你的代码太乱,不值得去花时间找bug。

你的解法和我的完全一样,惟一的区别就是你是复制了代码
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-7-31 14:40:05 | 显示全部楼层
北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧,  quick sort和merge sort都写了, 看注释。
你的代码太乱,不值得去花时间找bug。

顺便能问问是怎么复制代码的么
回复 支持 反对

使用道具 举报

weixc1234 发表于 2014-7-31 15:23:49 | 显示全部楼层
donnice 发表于 2014-7-31 14:40
顺便能问问是怎么复制代码的么

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

github是个好东西,嗯
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-7-31 15:57:29 | 显示全部楼层
weixc1234 发表于 2014-7-31 15:23
leetcode答案:https://github.com/soulmachine/leetcode

github是个好东西,嗯

诶,貌似只找到了C++的版本……
回复 支持 反对

使用道具 举报

weixc1234 发表于 2014-7-31 16:25:37 | 显示全部楼层
donnice 发表于 2014-7-31 15:57
诶,貌似只找到了C++的版本……

看看实现就行了 思想都是一样的

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

北美农民 发表于 2014-7-31 21:29:42 | 显示全部楼层
本帖最后由 北美农民 于 2014-7-31 08:32 编辑
donnice 发表于 2014-7-31 01:38
你的解法和我的完全一样,惟一的区别就是你是复制了代码

nlogn的排序能有什么别的思路? 而且思路一样, 用代码表达出来的不一样, bug-resistency也不一样。你写了不少可避免的代码, 这样的代码质量就算ac对于面试也不是好事, 更何况你也没ac。

我在qsort那留了个小破绽(不是bug), 不知道你能看出来么╮(╯▽╰)╭
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-8-1 00:58:02 | 显示全部楼层
本帖最后由 donnice 于 2014-8-1 01:04 编辑
北美农民 发表于 2014-7-31 21:29
nlogn的排序能有什么别的思路? 而且思路一样, 用代码表达出来的不一样, bug-resistency也不一样。你写 ...
你不会是想说append的return写错了吧。。。
回复 支持 反对

使用道具 举报

 楼主| donnice 发表于 2014-8-2 01:55:52 | 显示全部楼层
donnice 发表于 2014-8-1 00:58
你不会是想说append的return写错了吧。。。

诶,难道不该是先把cur赋给新的node,然后再return node.next么
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-8-2 19:56:54 | 显示全部楼层
北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧,  quick sort和merge sort都写了, 看注释。
你的代码太乱,不值得去花时间找bug。

那个,merge sort那部分有点没看懂啊,直接merge就能保证排好序了么?
回复 支持 反对

使用道具 举报

pyemma 发表于 2014-8-2 19:58:40 | 显示全部楼层
北美农民 发表于 2014-7-31 12:12
直接参考我的代码吧,  quick sort和merge sort都写了, 看注释。
你的代码太乱,不值得去花时间找bug。

抱歉,看错了,但是这样写merge sort是用递归来实现的,不是常数空间吧,我一开始也是使用递归的方法写的,但是这样做空间复杂度是O(LOGN)至少
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-3 00:00:51 | 显示全部楼层
pyemma 发表于 2014-8-2 06:58
抱歉,看错了,但是这样写merge sort是用递归来实现的,不是常数空间吧,我一开始也是使用递归的方法写的 ...

题目没要求常数空间啊。
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-3 00:16:59 | 显示全部楼层
pyemma 发表于 2014-8-2 06:58
抱歉,看错了,但是这样写merge sort是用递归来实现的,不是常数空间吧,我一开始也是使用递归的方法写的 ...

对了, 求一段 nlogn排序 + 常数空间的实现?  谢谢。
回复 支持 反对

使用道具 举报

Kimurate 发表于 2014-8-3 00:42:37 | 显示全部楼层
北美农民 发表于 2014-8-2 08:16
对了, 求一段 nlogn排序 + 常数空间的实现?  谢谢。

自底向上地 merge sort,可以 O(1) space,O(nlogn) time
不过实现很 tricky,感觉不必深究。
有兴趣可以看这里:
http://lifexplorer.me/leetcode-sort-list/
回复 支持 反对

使用道具 举报

北美农民 发表于 2014-8-3 01:02:43 | 显示全部楼层
Kimurate 发表于 2014-8-2 11:42
自底向上地 merge sort,可以 O(1) space,O(nlogn) time
不过实现很 tricky,感觉不必深究。
有兴趣可 ...

bottom up不tricky, 只是要一份implementation看看写的怎么样, 感觉很乱。

我记得在哪里看过真正应用中,O(logn)的栈空间复杂度是可以视为常数的效果。因为堆栈深度上限太有限了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-3 04:07

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表