148. Sort List 排序链表

@TOC

# 题目描述

Sort a linked list in O(n log 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
``````

# 解题方法

Merge排序就是先划分成一前一后等分的两块，然后对两块分别进行排序，然后再合并两个有序序列。

Python代码如下：

``````# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution(object):
"""
:rtype: ListNode
"""
while fast and fast.next:
pre = slow
slow = slow.next
fast = fast.next.next
pre.next = None
l2 = self.sortList(slow)
return self.mergeTwoLists(l1, l2)

def mergeTwoLists(self, l1, l2):
if not l1: return l2
if not l2: return l1
while l1 and l2:
if l1.val < l2.val:
move.next = l1
l1 = l1.next
else:
move.next = l2
l2 = l2.next
move = move.next
move.next = l1 if l1 else l2
``````

C++代码如下，对于链表操作全是指针操作，真的很烦：

``````/**
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
// make the list sort.
while (fast && fast->next) {
pre = slow;
fast = fast->next->next;
slow = slow->next;
}
pre->next = nullptr;
ListNode* l2 = sortList(slow);
return mergeList(l1, l2);
}
// merge two sort list.
ListNode* mergeList(ListNode* l1, ListNode* l2) {
if (!l1) return l2;
if (!l2) return l1;
ListNode* dummy = new ListNode(0);
ListNode* cur = dummy;
while (l1 && l2) {
if (l1->val < l2->val) {
cur->next = l1;
l1 = l1->next;
} else {
cur->next = l2;
l2 = l2->next;
}
cur = cur->next;
}
if (l1) cur->next = l1;
else  cur->next = l2;
return dummy->next;
}
};
``````

# 日期

2018 年 3 月 20 日 —— 阳光明媚～ 2019 年 1 月 11 日 —— 小光棍节？