一亩三分地论坛

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

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

[二分/排序/搜索] leetcode上的一道题 sort linked list

[复制链接] |试试Instant~ |关注本帖
macrofun 发表于 2015-10-9 17:11:21 | 显示全部楼层 |阅读模式

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

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

x
本帖最后由 macrofun 于 2015-10-9 17:16 编辑

Sort ListQuestion Solution

Total Accepted: 54682 Total Submissions: 239809 Difficulty: Medium

Sort a linked list in O(n log n) time using constant space complexity.









用的是归并排序,感觉不应该超时。但是提交后一直TLE
  1. /**
  2. * Definition for singly-linked list.
  3. * struct ListNode {
  4. *     int val;
  5. *     ListNode *next;
  6. *     ListNode(int x) : val(x), next(NULL) {}
  7. * };
  8. */
  9. class Solution {
  10. public:
  11.    
  12.     ListNode* getMidPtr(ListNode* head)
  13.     {
  14.         ListNode *mid = head;
  15.         ListNode *tail = head;
  16.         if(nullptr != tail->next && nullptr != tail->next->next)
  17.         {
  18.             mid = mid->next;
  19.             tail = tail->next->next;
  20.         }
  21.         return mid;
  22.         
  23.     }

  24.    
  25.      ListNode* sortList(ListNode* head) {
  26.         //使用归并排序来做
  27.         //用递归来做
  28.         if(nullptr == head || nullptr == head->next)
  29.             return head;
  30.         ListNode *mid = getMidPtr(head);
  31.         ListNode* next = mid->next;
  32.         
  33.         mid->next = nullptr;
  34.         
  35.         return mergeList(sortList(head), sortList(next));
  36.     }
  37.    
  38.     //链表l1和l2自身是有序的
  39.     ListNode* mergeList(ListNode* l1, ListNode* l2)
  40.     {
  41.         ListNode dummyHead(-1);
  42.         ListNode* hPtr = &dummyHead;
  43.         
  44.         while(nullptr != l1 && nullptr!= l2)
  45.         {
  46.             if(l1->val <= l2->val)
  47.             {
  48.                 hPtr->next = l1;
  49.                 hPtr = hPtr->next;
  50.                 l1 = l1->next;
  51.             }
  52.             else
  53.             {
  54.                 hPtr->next = l2;
  55.                 hPtr = hPtr->next;
  56.                 l2 = l2->next;
  57.             }
  58.         }
  59.         
  60.         if(nullptr == l1)
  61.             hPtr->next = l2;
  62.         else
  63.             hPtr->next = l1;
  64.         
  65.         return dummyHead.next;
  66.     }
  67.    
  68.     //std::stack<ListNode*> s;
  69. };
复制代码
求指点一下,应该怎么改进?感谢。
plich 发表于 2015-10-9 19:48:57 | 显示全部楼层
36行的递归有问题,编译调试一下就能会看出来了

sortList(head) 相当于又sort了一遍自己(而不是前半段),这是个无限循环……
回复 支持 反对

使用道具 举报

 楼主| macrofun 发表于 2015-10-9 21:34:22 | 显示全部楼层
本帖最后由 macrofun 于 2015-10-9 21:36 编辑
plich 发表于 2015-10-9 19:48
36行的递归有问题,编译调试一下就能会看出来了

sortList(head) 相当于又sort了一遍自己(而不是前半段 ...

36行 是对的。因为第34行mid->next = nullptr;
就把链表截成两段了。
不过还是十分感谢。
晚上吃完饭后又看了一眼程序,才发现是第16行错了。本来应该是while的,打成if了。

被坑爹了.jpg



回复 支持 反对

使用道具 举报

hkc593 发表于 2015-10-10 12:33:18 | 显示全部楼层
从算法上来说,就是个merge sort吧
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-6 03:03

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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