问题描述

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 listsListNode* 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)。