用python语言解答LeetCode的148题
方法一：归并排序（递归法）
- 题目要求时间空间复杂度分别为O(nlogn)和O(1),根据时间复杂度我们自然想到二分法，从而联想到归并排序；
对数组做归并排序的空间复杂度为O(n)，分别由新开辟数组O(n)和递归函数调用O(logn)组成，而根据链表特性：
- 数组额外空间：链表可以通过修改引用来更改节点顺序，无需像数组一样开辟额外空间
- 递归额外空间：递归调用函数将带来O(logn)的空间复杂度，因此若希望达到O(1)空间复杂度，则不能使用递归。
通过递归实现链表归并排序，有以下两个环节：
1.分割cut环节：找到当前链表中点，并从中点将链表断开（以便在下次递归cut时，链表片段拥有正确边界）；
- 我们使用fast，slow快慢双指针法，奇数个节点找到中点，偶数个节点找到中心左边的结点。
- 找到中点slow后，执行slow.next = None将链表切断。
- 递归分割时，输入当前链表左端点head和中心节点slow的下一个节点tmp（因为链表是从slow切断的）
- cut递归终止条件：当head.next == None时，说明只有一个节点了，直接返回节点。
2.合并merge环节: 将两个排序链表合并，转化为一个排序链表。
- 双指针合并，建立辅助ListNode h作为头部。
- 设置两个指针left、right分别指向两个链表头部，比较两个指针处结点值大小，由小到大加入合并链表头部，指针交替前进，直至添加完两个链表。
- 返回辅助ListNode h作为头部的下一个节点h.next
- 时间复杂度O(l+r)，l,r分别代表两个链表长度。
当题目输入的head==None时，直接返回None
方法一的代码实现：
#coding:utf-8
class ListNode:
def __init__(self, val):
self.val = val
self.next = next
class Solution:
def sortList(self, head):
if not head or not head.next:
return head
slow , fast = head, head.next
while fast and fast.next:
fast, slow = fast.next.next, slow.next
mid, slow.next = slow.next, None
left, right = self.sortList(head), self.sortList(mid)
h = res = ListNode(0)
while left and right:
if left.val < right.val:
h.next, left = left, left.next
else:
h.next, right = right, right.next
h = h.next
h.next = left if left else right
return res.next
Reference：
1.精选题解Sort List （归并排序链表）
https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/
