一、链表排序
1、归并排序（递归版）
这个算法要采用递归，空间复杂度没办法达到O(n),时间复杂度为O(nlog(n)
# -*- coding: utf-8 -*-'
class ListNode(object):
def __init__(self, x):
self.val = x
self.next = None
class Solution(object):
def sortList(self, head):
if not head or not head.next:
return head
prev, slow, fast = None, head, head
while fast and fast.next:
prev, slow, fast = slow, slow.next, fast.next
prev.next = None # 将链表切断，分为head和slow两条子链
"""
等价以下代码
l1 = self.sortList(head)
l2 = self.sortList(slow)
return self.merge(l1, l2)
"""
return self.merge(*map(self.sortList, (head, slow)))
def merge(self, l1, l2):
dummy = l = ListNode(None)
while l1 and l2:
if l1.val < l2.val:
l.next, l, l1 = l1, l1, l1.next
else:
l.next, l, l2 = l2, l2, l2.next
l.next = l1 or l2
"""
l1,l2长度不一样时，l.next为l1,l2中比另一个长度长的子链
如 l1: 1->2 l2: 3->4->5, l.next为5
等价于以下代码
if l1:
l.next = l1
else:
l.next = l2
"""
return dummy.next
if __name__ == "__main__":
s = Solution()
l = head = ListNode(None)
for val in [0, 4, 1, 6, 7]:
l.next = ListNode(val)
l = l.next
li = s.sortList(head.next)
while li:
print li.val
li = li.next
2、快速排序
这个算法比归并排序复杂，速度比归并排序快50%左右，但是没看懂，以后再细细研究
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
def partition(start, end):
node = start.next.next
pivotPrev = start.next
pivotPrev.next = end
pivotPost = pivotPrev
while node != end:
temp = node.next
if node.val > pivotPrev.val:
node.next = pivotPost.next
pivotPost.next = node
elif node.val < pivotPrev.val:
node.next = start.next
start.next = node
else:
node.next = pivotPost.next
pivotPost.next = node
pivotPost = pivotPost.next
node = temp
return [pivotPrev, pivotPost]
def quicksort(start, end):
if start.next != end:
prev, post = partition(start, end)
quicksort(start, prev)
quicksort(post, end)
newHead = ListNode(0)
newHead.next = head
quicksort(newHead, None)
return newHead.next
3、投机取巧法（但是速度真的很快，leetcode打败98.59%）
此算法比较取巧，使用一个列表临时存储链表中的值。
第一次遍历链表，将链表中的值顺序存储到列表中，第二次遍历链表，将排序后的列表的值放入链表中，时间复杂度为O(2n),空间复杂度应该为O(2n)，时间复杂度为O(n)
class Solution(object):
def sortList(self, head):
"""
:type head: ListNode
:rtype: ListNode
"""
if not head or not head.next:
return head
temp = head
node_list = []
while head:
node_list.append(head.val)
head = head.next
node_list.sort()
head = temp
i = 0
while head:
head.val = node_list[i]
head = head.next
i += 1
return temp