首页 > 其他 > 详细

LeetCode 148. Sort List

时间:2018-07-29 00:35:53      阅读:201      评论:0      收藏:0      [点我收藏+]

归并排序的应用。本题将一个链表分为两个有个技巧,就是快慢两个指针,需要注意的是如果一开始 slow=fast=head 来做,后面是 fast=slow->next; slow->next=NULL 的话在两个元素的时候会死循环,因此要么改前面要么改后面。

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head==NULL || head->next==NULL) return head;
        ListNode *slow=head, *fast=head->next;
        while (fast!=NULL && fast->next!=NULL){
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        return merge(sortList(head), sortList(fast));
    }
    
    ListNode *merge(ListNode *left, ListNode *right){
        ListNode *dummy=new ListNode(0);
        ListNode *p=left, *q=right, *r=dummy;
        while (p!=NULL && q!=NULL){
            if (p->val<q->val){r->next=p; p=p->next;}
            else {r->next=q; q=q->next;}
            r = r->next;
        }
        while (p!=NULL){r->next=p; p=p->next; r=r->next;}
        while (q!=NULL){r->next=q; q=q->next; r=r->next;}
        return dummy->next;
    }
};

 

LeetCode 148. Sort List

原文:https://www.cnblogs.com/hankunyan/p/9383959.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!