题解 | #单链表的排序#

单链表的排序

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

class Solution {
public:
    ListNode* sortInList(ListNode* head) {
        // write code here
        if(head == nullptr || head->next==nullptr) return head;
        ListNode* slow,*fast,*pre;
        pre = head;
        slow = head->next;
        fast = head->next->next;
        while(fast!=nullptr && fast->next!=nullptr) {
            pre = pre->next;
            slow = slow->next;
            fast = fast->next->next;
        }
        pre->next = nullptr;
        ListNode* sortedHead = sortInList(head);
        ListNode* sortedSlow = sortInList(slow);
        return merge(sortedHead, sortedSlow);
    }
    ListNode* merge(ListNode* p,ListNode* q){
        if(p==nullptr) return q;
        if(q==nullptr) return p;
        if(p->val < q->val){
            p->next = merge(p->next, q);
            return p;
        }
        else{
            q->next = merge(p, q->next);
            return q;
        }
    }
};

https://www.cnblogs.com/grandyang/p/4249905.htmlhttps://www.cnblogs.com/grandyang/p/4249905.html
全部评论

相关推荐

快点约我面试吧
投递百度等公司10个岗位
点赞 评论 收藏
分享
每晚夜里独自颤抖:你cet6就cet6,cet4就cet4,你写个cet证书等是什么意思。专业技能快赶上项目行数,你做的这2个项目哪里能提现你有这么多技能呢
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务