# LeetCode148. Sort List（链表 / 模拟）

## LeetCode148. Sort List（链表 / 模拟）

• Medium
• Accepted：170,901
• Submissions：502,827

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

Example 1:

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

Example 2:

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

### 链接

https://leetcode.com/problems/sort-list

### 代码

• Runtime: 76 ms, faster than 29.31% of C++ online submissions for Sort List.
• Memory Usage: 28.8 MB, less than 8.79% of C++ online submissions for Sort List.
// 递归形式
// 时间复杂度 O(nlogn)
// 空间复杂度 O(logn)

/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
while (fast && fast->next) // slow作为中间的结点
{
slow = slow->next;
fast = fast->next->next;
}
slow->next = NULL;
}

private:
ListNode* merge(ListNode* a, ListNode* b)
{
ListNode* p1 = a;
ListNode* p2 = b;
while (p1 && p2)
{
if (p1->val < p2->val)
{
p->next = p1;
p1 = p1->next;
}
else
{
p->next = p2;
p2 = p2->next;
}
p = p->next;
p->next = NULL;
}
if (p1)  // 剩余所有元素
p->next = p1;
if (p2)
p->next = p2;

};