题目描述

给一个单链表排序，要求时间 $O(nlogn)$，空间 $O(1)$

算法

(归并排序) 时间复杂度 $O(nlogn)$， 空间复杂度 $O(logn)$

对于数组而言，$O(nlogn)$ 时间复杂度的算法为，快速排序/堆排序/归并排序，三者的空间复杂度分别为 $O(logn)/O(1)/O(n)$; 对于链表而言，采用归并排序不需要额外的空间来存放排序后的结果，但递归需要用到系统栈，因此空间复杂度为 $O(logn)$。

本题可利用21. Merge Two Sorted Lists的代码。

1. 利用快慢指针将输入链表平分成两个链表
2. 递归调用sortList()对这两个链表分别排序
3. 调用mergeTwoLists()来合并两个有序链表

C++ 代码

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        // corner case
        if(head == nullptr || head->next ==nullptr) return head;

        // 找中间节点
        ListNode* fast = head;
        ListNode* slow = head;
        while(fast->next != nullptr && fast->next->next !=nullptr){
            fast = fast->next->next;
            slow = slow->next;
        }

        // slow指向中间节点，现在需要把前后段分开
        fast = slow;
        slow = slow->next;
        fast->next = NULL;

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

        return mergeTwoLists(left,right);
    }

    // 21. Merge Two Sorted Lists  
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(0);
        ListNode *cur = dummy;
        while (l1 != NULL && l2 != NULL) {
            if (l1 -> val < l2 -> val) {
                cur -> next = l1;
                l1 = l1 -> next;
            }
            else {
                cur -> next = l2;
                l2 = l2 -> next;
            }
            cur = cur -> next;
        }
        cur -> next = (l1 != NULL ? l1 : l2);
        return dummy -> next;
    }
};