https://leetcode-cn.com/explore/interview/card/bytedance/244/linked-list-and-tree/1040/
image.png
要求用O(nlogn)复杂度的排序，只有归并比较适合
在归并中注意递归的merge的时机
在链表一分为二的时候，用一个慢节点和快节点跑步来找
代码如下：
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
p = head
p2 = p.next.next
while p2:
if not p2.next or not p2.next.next:
break
p = p.next
p2 = p2.next.next
p_right = p.next
p.next = None
left = self.sortList(head)
right = self.sortList(p_right)
return self.mergeList(left,right)
def mergeList(self,l1,l2):
if not l1:
return l2
if not l2:
return l1
new_list = None
head = None
while l1 and l2:
tmp_node = l1
if l1.val>l2.val:
tmp_node = l2
l2 = l2.next
else:
l1 = l1.next
if not new_list:
new_list = ListNode(tmp_node.val)
head = new_list
else:
next_node = ListNode(tmp_node.val)
new_list.next = next_node
new_list = next_node
if l1:
new_list.next = l1
if l2:
new_list.next = l2
return head
