题目描述

给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。
在 $O(nlogn)$ 时间复杂度和常数级空间复杂度下，对链表进行排序。

样例

输入: 4->2->1->3
输出: 1->2->3->4

输入: -1->5->3->4->0
输出: -1->0->3->4->5

迭代归并排序

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

空间复杂度 : $O(1)$

C++ 代码

/**
 * 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) return head;

        int len = 0;
        auto node = head;

        while (node) node = node->next, len ++ ;            //遍历得出链表长度

        auto dummy = new ListNode(0, head);
        for (int sublen = 1; sublen < len; sublen <<= 1)    //子链表长度每次翻倍，这层循环复杂度为O(logN)
        {
            auto pre = dummy, cur = dummy->next;
            while (cur)                     //这层循环复杂度为O(N)，故总时间复杂度为O(NlogN)
            {
                auto head1 = cur;           //定义第一段头节点
                for (int i = 1; i < sublen && cur->next; i ++ )
                    cur = cur->next;        //得到第一段尾节点

                auto head2 = cur->next;     //定义第二段头节点
                cur->next = NULL;           //切掉第一段

                cur = head2;                //开始找第二段尾节点
                for (int i = 1; i < sublen && cur && cur->next; i ++ )
                    cur = cur->next;

                ListNode* next = NULL;
                if (cur)
                {
                    next = cur->next;       //标记第三段（下一次循环的第一段）的起始节点
                    cur->next = NULL;       //切掉第二段
                }

                ListNode* merged = merge(head1, head2);     //合并当前两段

                pre->next = merged;                         //pre用来连接合并后的段
                while (pre->next) pre = pre->next;          

                cur = next;                                 //开始第三段
            }
        }

        return dummy->next;
    }

    ListNode* merge(ListNode* l1, ListNode* l2)     //两个有序链表合并模板
    {
        auto dummy = new ListNode(-1), p = dummy;

        while (l1 && l2)
        {
            if (l1->val < l2->val)
            {
                p = p->next = l1;
                l1 = l1->next;
            }
            else
            {
                p = p->next = l2;
                l2 = l2->next;
            }
        }

        if (l1) p->next = l1;
        if (l2) p->next = l2;

        return dummy->next;
    }
};