欢迎访问LeetCode题解合集

题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。

进阶：

• 你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？

示例 1：

[HTML_REMOVED]

[HTML_REMOVED]

输入：head = [4,2,1,3]
输出：[1,2,3,4]

示例 2：

[HTML_REMOVED]

[HTML_REMOVED]

输入：head = [-1,5,3,4,0]
输出：[-1,0,3,4,5]

示例 3：

输入：head = []
输出：[]

提示：

• 链表中节点的数目在范围 [0, 5 * 10^4] 内

• -10^5 <= Node.val <= 10^5

题解：

$O(nlogn)$ 时间复杂度可以考虑：快排、堆排、归并排序。在对链表操作时，堆排的空间复杂度为 $O(n)$，堆排可以不考虑。

法一：

快排。

时间复杂度：$O(nlogn)$，最坏情况退化为 $O(n^2)$

额外空间复杂度：$O(logn)$

交换值版本：

数组版本的快速排序是两个指针相对移动，而对于链表，可以两个指针同向移动。

参考 单链表的快速排序

/**
 * 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) {
        if ( !head || !head->next ) return head;
        quickSort( head, nullptr );
        return head;
    }

    void quickSort( ListNode* begin, ListNode* end ) {
        if ( begin == end || begin->next == end ) return;

        int pivot = begin->val;
        ListNode *p = begin, *q = p->next;
        while ( q != end ) {
            if ( q->val < pivot ) {
                p = p->next;
                swap( p->val, q->val );
            }
            q = q->next;
        }
        swap( begin->val, p->val );
        quickSort( begin, p );
        quickSort( p->next, end );
    }
};
/*
时间：1836ms，击败：5.12%
内存：28.3MB，击败：99.40%
*/

交换节点版本：

根据关键字将链表拆成三部分，然后合并。

但是，超时了。。。。

/**
 * 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* getTail(ListNode *head) {
        while (head->next)
            head = head->next;
        return head;
    }
    ListNode* sortList(ListNode* head) {
        if ( !head || !head->next ) return head;

        ListNode lhead, mhead, rhead;
        ListNode *l = &lhead, *m = &mhead, *r = &rhead;
        int pivot = head->val;
        for( auto p = head; p; p = p->next ) {
            if ( p->val < pivot )
                l = l->next = p;
            else if ( p->val > pivot )
                r = r->next = p;
            else
                m = m->next = p;
        }

        l->next = m->next = r->next = nullptr;

        (&lhead)->next = sortList( (&lhead)->next );
        (&rhead)->next = sortList( (&rhead)->next );

        getTail(&lhead)->next = (&mhead)->next;
        m->next = (&rhead)->next;

        return (&lhead)->next;
    }
};

法二：

归并排序。

分为两种：自顶向下和自底向上。

自顶向下需要递归 $O(logn)$ 空间复杂度，自底向上只需要 $O(1)$ 的空间。

自顶向下：

快慢指针找中间节点，然后递归左右两部分。

时间复杂度：$O(nlogn)$

额外空间复杂度：$O(nlogn)$

/**
 * 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) {
        if ( !head || !head->next ) return head;

        ListNode *f = head->next, *s = head;
        while ( f && f->next ) {
            f = f->next->next;
            s = s->next;
        }
        f = s->next;
        s->next = nullptr;

        ListNode *left = sortList( head );
        ListNode *right = sortList( f );

        return mergeTwoLists( left, right );
    }

    ListNode* mergeTwoLists( ListNode* h1, ListNode* h2 ) {
        ListNode dummy;
        ListNode *cur = &dummy;
        while ( h1 && h2 ) {
            if ( h1->val <= h2->val ) {
                cur->next = h1;
                h1 = h1->next;
            } else {
                cur->next = h2;
                h2 = h2->next;
            }
            cur = cur->next;
        }
        if ( h1 ) cur->next = h1;
        else cur->next = h2;
        return (&dummy)->next;
    }
};
/*
时间：104ms，击败：97.65%
内存：28.3MB，击败：97.37%
*/

自底向上：

迭代 $logn$ 次，每次迭代将链表分为 $n / {2^i}$ 份，相邻两份二路归并，最后就是一个完整的有序链表。（注意：不能整除剩余的节点单独成一份）

时间复杂度：$O(nlogn)$

额外空间复杂度：$O(1)$

/**
 * 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) {
        if ( !head || !head->next ) return head;

        int n = 0;
        ListNode *p = head;
        for (; p; p = p->next, ++n );

        ListNode *dummy = new ListNode();
        dummy->next = head;

        ListNode *cur = nullptr, *q = nullptr;
        for ( int i = 1; i < n; i <<= 1 ) {
            cur = dummy;
            for ( int j = 0; j + i <= n; j += (i << 1) ) {
                p = cur->next, q = p;
                for ( int k = 0; k < i; ++k ) q = q->next;
                int x = 0, y = 0;
                while ( x < i && y < i && p && q ) {
                    if ( p->val <= q->val ) {
                        cur->next = p;
                        p = p->next;
                        ++x;
                    } else {
                        cur->next = q;
                        q = q->next;
                        ++y;
                    }
                    cur = cur->next;
                }
                while ( x < i && p ) cur = cur->next = p, p = p->next, ++x;
                while ( y < i && q ) cur = cur->next = q, q = q->next, ++y;
                cur->next = q;
            }
        }
        return dummy->next;
    }
};
/*
时间：104ms，击败：97.65%
内存：28.3MB，击败：97.62%
*/