记录一道链表排序的题目，需要在(O nlog n)的时间复杂度以及固定的空间复杂度
Sort a linked list in O(n log n) time using constant space complexity.
这道题暴力来做的话，就是遍历，最差的情况下，复杂度为O(n^2)
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
head_pointer = head
pre_pointer = head
head = head.next
while head:
pre, tmp = None, head_pointer
while head.val > tmp.val and tmp != head:
pre = tmp
tmp = tmp.next
if not pre:
pre_pointer.next = head.next
head.next = head_pointer
head_pointer = head
head = pre_pointer.next
continue
if tmp == head:
pre_pointer = head
head = head.next
continue
next_pointer = head.next
pre.next = head
head.next = tmp
pre_pointer.next = next_pointer
head = next_pointer
return head_pointer
上面这种做法，submit后超时，仔细分析一下，链表很适合用归并排序来做
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
fast, slow = head.next, head
while fast and fast.next:
fast = fast.next.next
slow = slow.next
second = slow.next
slow.next = None
l = self.sortList(head)
r = self.sortList(second)
return self.merge(l, r)
def merge(self, l, r):
if not l or not r:
return l or r
if l.val > r.val:
l, r = r, l
head, pre = l, l
l = l.next
while l and r:
if l.val < r.val:
pre.next = l
l = l.next
else:
pre.next = r
r = r.next
pre = pre.next
pre.next = l or r
return head