问题描述

Sort a linked list in O(n log n) time using constant space complexity.

算法分析

1、要求时间复杂度为 O(n log n)，可以考虑归并与快排；

2、本文使用归并，每次将链表从中间位置切断，一分为二；

3、递归2过程，直到链表长度为1；

4、依次从小到大合并两个链表，最后返回排序好的链表。

C++实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
    ListNode* mergeList(ListNode* head1, ListNode* head2) {
        shared_ptr<ListNode> newHead(new ListNode(0));
        ListNode* p = newHead.get();
        while (head1 && head2) {
            if (head1->val <= head2->val) {
                p->next = head1;
                head1 = head1->next;
            }
            else {
                p->next = head2;
                head2 = head2->next;
            }
            p = p->next;
        }
        p->next = !head1 ? head2 : head1;
        return newHead->next;
    }
public:
    ListNode* sortList(ListNode* head) {
        if (!head || !head->next)
            return head;

        //devide into two lists
        ListNode* slow = head,
            *fast = head->next;
        while (fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = nullptr;

        return mergeList(sortList(head), sortList(fast));
    }
};

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