Leetcode148. 排序链表(HOT100)

链接

我写的错误代码：

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next)
            return head;
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast&&fast->next) {
            fast = fast->next->next;
            slow = slow->next;
        }

        ListNode* p = sortList(head);
        ListNode* q = sortList(slow);
        return merge(p, q);
    }
    ListNode* merge(ListNode* p, ListNode* q) {
        ListNode* head = new ListNode(-1);
        while (p && q) {
            if (p->val <= q->val) {
                ListNode* cur = p->next;
                p->next = head->next;
                head->next = p;
                p = p->next;
            } else {
                ListNode* cur = q->next;
                q->next = head->next;
                head->next = q;
                q = q->next;
            }
        }

        ListNode* tail = head;
        while (tail->next) {
            tail = tail->next;
        }
        tail->next = p ? p : q;
        return head->next;
    }
};

 正确代码如下：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int n = 0;
        for(auto p = head;p;p = p->next)++n;
        for(int i = 1;i<n;i*=2){//刚开始每段只有一个节点，最后一次每段有大约一半节点，合并成最后的答案
            auto dummy = new ListNode(-1),cur = dummy;
            for(int j = 1;j<=n;j+=i*2){
                auto p = head,q = p;
                for(int k = 0;k<i&&q;k++) q = q->next;
                auto o = q;
                for(int k = 0;k<i&&o;k++)o = o->next;
                int l = 0,r = 0;
                while(l<i && r<i && p && q){
                    if(p->val<=q->val)cur = cur->next = p,p = p->next,l++;
                    else cur = cur->next = q,q = q->next,r++;
                }
                while(l<i && p){
                    cur = cur->next = p;
                    p = p->next;
                    l++;
                }
                while(r<i && q){
                    cur = cur->next = q;
                    q = q->next;
                    r++;
                }
                head = o;
            }
            cur->next = nullptr;
            head = dummy->next;
            dummy->next = nullptr;//
            delete dummy;//
        }
        return head;
    }
};

这是自底向上归并排序写法。 

图示：

上图cur也要跟随移动。

第二轮：
 

总体图示就这样的。q是依靠p推出来的，刚开始跳1步，然后跳2步........

o是为了记录下一次应该继续排序的位置。

dummy是一个虚拟头结点，cur用来维护它的尾，至于谁往cur->next插入，要看p q指向的节点谁的值小。

每一轮完了后，让head重新回归dummy的next，然后cur->next=nullptr；即将尾置空。