题解 | #单链表的排序#

单链表的排序

http://www.nowcoder.com/practice/f23604257af94d939848729b1a5cda08

归并排序的样板代码,主要是合并两个链表的部分,以及要注意在归并前需要断开链表,否则会死循环。

#include<iostream>
#include<vector>
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

class Solution {
public:
    ListNode* mergeSort(ListNode* head) {
        if(head==NULL || head->next==NULL)
            return head;
        ListNode *fast = head, *slow = head, *pre;
        while(fast && fast->next) {
            pre = slow;
            fast = fast->next->next;
            slow = slow->next;
        }
        pre->next = NULL;
        ListNode* left = mergeSort(head);
        ListNode* right = mergeSort(slow);
        ListNode* dummy = new ListNode(0);
        ListNode* p = dummy;
        while(left || right) {
            if(left == NULL || (right && right->val < left->val)) {
                p->next = right;
                right = right->next;
            }
            else{
                p->next = left;
                left = left->next;
            }
            p = p->next;
        }
        return dummy->next;
    }
    ListNode* sortInList(ListNode* head) {
        return mergeSort(head);
    }
};
全部评论

相关推荐

头像
今天 11:23
已编辑
北京邮电大学 管理咨询
211勇闯初创小公司头破血流系列3这件事不是发生在我身上的,但前同事们参与创作的积极性空前高涨,为了习惯,还是都采用第一人称的视角来看这出大戏。有一天老板在我们的眼皮底下接了一个电话,最终敲定了去北京出差的时间,下周一。他得意洋洋地说,这单下来保底五百万的流水,如果成了,我们都能得到五位数的提成。这对于一群刚上班的人来说是天大的诱惑,我们经历了周末的无偿加班,把他去北京所需要的文件都准备好了。只是在去北京的周一当天,老板睡过头了。整个上午都没见他的踪影,给他发文件也不会,打电话问问题也不接,直到中午才姗姗来迟。当然,这只是拉开了这场恐怖出差的序幕。只见他来了也不紧不慢的,手指在办公室转了一圈,...
姜大力:补充: 1.五百万的单子根本没有五百万,只是过去展示拼装的产品并简单考察。该项目只是竞标,项目内容是商业街区改造; 2.决策是当天上午10点半左右老板珊珊来迟后突发奇想去北京,中午1点在催促下着急出发,没有任何出差补助; 3.出发之前已经知道进京证不好使了,但还是执意要开车去; 4.实习生实打实连续开了***小事车,非常辛苦,工资在转正后只有两千五; (有疑问会继续补充)
点赞 评论 收藏
分享
Lyxiho:浙江大学 加大加粗
点赞 评论 收藏
分享
评论
2
收藏
分享

创作者周榜

更多
牛客网
牛客企业服务