本文共 1601 字，大约阅读时间需要 5 分钟。

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

Example 1:

Input: 4->2->1->3Output: 1->2->3->4

Example 2:

Input: -1->5->3->4->0Output: -1->0->3->4->5

解析：

先将链表分成两部分，然后在合并这两部分链表

代码：

/** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode(int x) : val(x), next(NULL) {} * }; */class Solution {public:    ListNode* merge(ListNode* left, ListNode* right)//合并两部分链表    {        ListNode* head = new ListNode(-1);        ListNode* pre = head;        while(left != nullptr && right != nullptr)        {            if(left->val <= right->val)            {                pre->next = left;                pre = left;                left = left->next;            }            else            {                pre->next = right;                pre = right;                right = right->next;            }        }        if(left != nullptr)            pre->next = left;        if(right != nullptr)            pre->next = right;                return head->next;    }    ListNode* sortList(ListNode* head) {        if(head == nullptr || head->next == nullptr)            return head;        ListNode* pre = nullptr;        ListNode* slow = head;        ListNode* fast = head;        //将链表分成两部分        while(fast != nullptr && fast->next != nullptr)        {            pre = slow;            slow = slow->next;            fast = fast->next->next;        }        pre->next = nullptr;//将链表断开，slow为后面一个链表的头        ListNode* left = sortList(head);        ListNode* right = sortList(slow);                return merge(left, right);    }};

转载地址：http://ytwab.baihongyu.com/