148.排序链表

题目描述

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

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

方法一：自顶向下归并排序

算法思想：

1. 找到链表的中点，以中点为分界，将链表拆分成两个子链表。
2. 对两个子链表分别排序。
3. 将两个排序后的子链表合并，得到完整的排序后的链表。

/*
    链表的归并排序
    head：子链表串的第一个结点
    tail：子链表串最后一个结点的后一个结点
*/
ListNode *sortList(ListNode *head, ListNode *tail)
{
    // 递归退出条件，即划分至只有一个结点
    if (head->next == tail)
    {
        head->next = nullptr; // 断链
        return head;
    }

    // 使用快慢指针找出链表的 mid 结点
    // slow 最终得到的是真实 mid 的后一个结点
    // fast 最终得到的是最后一个结点的后一个结点
    ListNode *fast = head;
    ListNode *slow = head;
    while (fast != tail)
    {
        fast = fast->next;
        slow = slow->next;
        if (fast != tail)
            fast = fast->next;
    }

    ListNode *mid = slow;    // mid 是第二个链表的头结点
    return mergeList(sortList(head, mid), sortList(mid, tail));
}

/*
    将两个有序链表合并成一个有序链表，返回合并链表头指针
*/
ListNode *mergeList(ListNode *list1, ListNode *list2)
{
    ListNode *dummyHead = new ListNode(0);
    ListNode *merge_temp = dummyHead;
    ListNode *list1_temp = list1;
    ListNode *list2_temp = list2;
    while (list1_temp && list2_temp)
    {
        if (list1_temp->val <= list2_temp->val)
        {
            merge_temp->next = list1_temp;
            list1_temp = list1_temp->next;
        }
        else
        {
            merge_temp->next = list2_temp;
            list2_temp = list2_temp->next;
        }
        merge_temp = merge_temp->next;
    }

    if (list1_temp)
        merge_temp->next = list1_temp;

    if (list2_temp)
        merge_temp->next = list2_temp;

    return dummyHead->next;
}

时间复杂度：O(nlogn)
空间复杂度：O(logn)

方法二：自底向上归并排序

算法思想：

1. 用 subLength 表示每次需要排序的子链表的长度，初始时 subLength=1。
2. 每两个子链表作为一组进行合并。划出子链表时断链，合并完之后再建链。
3. 将 subLength 值加倍，重复第二步，直至整个链表分成两个子链表并合并完。

ListNode *sortList2(ListNode *head)
{
    if (!head)
        return head;

    int length = 0;         // 链表总长度
    ListNode *node = head;
    while (node)
    {
        length++;
        node = node->next;
    }

    ListNode *dummyHead = new ListNode(0, head);    // 指向第一个结点

    // 自底向上合并
    for (int subLeng = 1; subLeng < length; subLeng <<= 1)
    {
        ListNode *prev = dummyHead;
        ListNode *cur = dummyHead->next;    // 整个链表遍历结点，确保一次遍历
        
        while (cur)
        {
            ListNode *head1 = cur;  // 第一次子链表头

            for (int i = 1; i < subLeng && cur != nullptr && cur->next != nullptr; i++)     // 遍历完第一个 subLength 长度的子链表
                cur = cur->next;

            ListNode *head2 = cur->next;    // 第二个子链表头
            cur->next = nullptr;    // 第一个 subLength 长度子链表断链
            cur = head2;            

            for (int i = 1; i < subLeng && cur != nullptr && cur->next != nullptr; i++)     // 遍历完第二个 subLength 长度的子链表
                cur = cur->next;

            ListNode *next = nullptr;  // 剩余未两两归并结点的首结点

            if (cur)    // 存在第二个子链表
            {
                next = cur->next;
                cur->next = nullptr;    //  断链
                cur = next;
            }

            ListNode *merged = mergeList(head1,head2);  // 合并一组子链表
            prev->next = merged;    // 建链，将每组链表重新建链
            while(prev->next)
                prev = prev->next;
        }
    }
    return dummyHead->next;
}

时间复杂度：O(nlogn)
空间复杂度：O(1)