一、链表排序
1、归并排序（递归版）
这个算法要采用递归，空间复杂度没办法达到O(n),时间复杂度为O(nlog(n)
# -*- coding: utf-8 -*-'class ListNode(object): def __init__(self, x): self.val = x self.next = Noneclass 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.nextif __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