50 链表排序（Sort List）

• • 1 题目
  • 2 解决方案
  • • 2.1 思路
    • 2.2 时间复杂度
    • 2.4 空间复杂度
  • 3 源码

题目：链表排序（Sort List）
描述：在 O(nlogn) 时间复杂度和常数级的空间复杂度下给链表排序。

lintcode题号——98，难度——medium

样例1：

输入：list = 1->3->2->null
输出：1->2->3->null
解释：给链表排序.

样例2：

输入：list = 1->7->2->6->null
输出：1->2->6->7->null
解释：给链表排序.

  题目要求排序，在O(nlogn)时间复杂度内，空间复杂度要求常数级，满足时间复杂度的排序可以想到快速排序和归并排序，满足空间复杂度的只有快速排序，但题目排序的对象是链表，归并排序在数组上的空间复杂度是O(n)，但对链表排序时不需要额外的数据结构来存储临时数据，所以在链表上的归并排序的空间复杂度只有O(1)，本题使用快排和归并都可以。

  时间复杂度为O(n * log n)。

  空间复杂度为O(1)。

细节：

1. 使用快、慢指针的方式来找链表的中点。
2. fast指针起点位置向后移动一位，符合整数计算偏左的特点，且不用特殊处理链表长度为2的情况。
3. 递归时先处理后半段，再将中点赋空，断开后半段，再处理前半段。

C++版本：

ListNode* sortList(ListNode *head) {
    // write your code here
    if (head == nullptr || head->next == nullptr) // 跳过链表长度为0和1的情况
    {
        return head;
    }

    // 找到链表中点
    ListNode * mid = head;
    ListNode * fast = head->next; // fast指针起点位置向后移动一位，符合整数计算偏左的特点，且不用特殊处理链表长度为2的情况
    while (fast != nullptr && fast->next != nullptr)
    {
        mid = mid->next;
        fast = fast->next->next;
    }

    ListNode * right = sortList(mid->next); // 先排后半段
    mid->next = nullptr; // 断开后半段
    ListNode * left = sortList(head); // 再排前半段

    return mergeTwoSortedList(left, right);
}

ListNode * mergeTwoSortedList(ListNode * left, ListNode * right)
{
    if (left == nullptr)
    {
        return right;
    }
    if (right == nullptr)
    {
        return left;
    }

    ListNode dummyNode(0);
    ListNode * cur = &dummyNode;
    while (left != nullptr && right != nullptr)
    {
        if (left->val < right->val)
        {
            cur->next = left;
            left = left->next;
            cur = cur->next;
        }
        else
        {
            cur->next = right;
            right = right->next;
            cur = cur->next;
        }
    }

    if (left != nullptr)
    {
        cur->next = left;
    }
    if (right != nullptr)
    {
        cur->next = right;
    }

    return dummyNode.next;
}