题解 | #单链表的排序#

呜呜呜呜呜，辛辛苦苦写的快排，结果过不了呜呜呜呜呜！！！！样例太刁钻了吧，归并也就是最坏情况比快排好而已啊。。。

class Solution {
  public:
    //合并两段有序链表
    ListNode* merge(ListNode* pHead1, ListNode* pHead2) {
        //一个已经为空了，直接返回另一个
        if (pHead1 == NULL)
            return pHead2;
        if (pHead2 == NULL)
            return pHead1;
        //加一个表头
        ListNode* head = new ListNode(0);
        ListNode* cur = head;
        //两个链表都要不为空
        while (pHead1 && pHead2) {
            //取较小值的节点
            if (pHead1->val <= pHead2->val) {
                cur->next = pHead1;
                //只移动取值的指针
                pHead1 = pHead1->next;
            } else {
                cur->next = pHead2;
                //只移动取值的指针
                pHead2 = pHead2->next;
            }
            //指针后移
            cur = cur->next;
        }
        //哪个链表还有剩，直接连在后面
        if (pHead1)
            cur->next = pHead1;
        else
            cur->next = pHead2;
        //返回值去掉表头
        return head->next;
    }

    ListNode* sortInList(ListNode* head) {
        //链表为空或者只有一个元素，直接就是有序的
        if (head == NULL || head->next == NULL)
            return head;
        ListNode* left = head;
        ListNode* mid = head->next;
        ListNode* right = head->next->next;
        //右边的指针到达末尾时，中间的指针指向该段链表的中间
        while (right != NULL && right->next != NULL) {
            left = left->next;
            mid = mid->next;
            right = right->next->next;
        }
        //左边指针指向左段的左右一个节点，从这里断开
        left->next = NULL;
        //分成两段排序，合并排好序的两段
        return merge(sortInList(head), sortInList(mid));
    }
};

虽然快排过不了，但也记录在这儿吧。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param head ListNode类
     * @return ListNode类
     */
    ListNode* sortInList(ListNode* head) {
        // write code here
        ListNode* p = head->next;
        // ListNode* secondhead = head->next;
        ListNode* prior = head;
        prior->next = NULL;
        if (p == NULL) return head;

        ListNode* lefthead = new ListNode(0);
        ListNode* righthead = new ListNode(0);
        ListNode* left = lefthead;
        ListNode* right = righthead;
        // p = secondhead;
        ListNode* tail;
        while (p) {
            tail = p->next;
            p->next = NULL;
            if (p->val < prior->val) {
                left->next = p;
                left = left->next;
            }
            else {
                right->next = p;
                right = right->next;
            }
            p = tail;
        }
        if (lefthead->next == NULL) {
            lefthead = prior;
            left = lefthead;
        }
        else {
            lefthead = sortInList(lefthead->next);
            for (left = lefthead; left->next != NULL; left = left->next) {}
            left->next = prior;
            left = left->next;
        }

        if (righthead->next == NULL) {
            righthead = NULL;
        }
        else {
            righthead = sortInList(righthead->next);
        }
        left->next = righthead;

        return lefthead;
    }
};