来源：https://leetcode.com/problems/sort-list
Sort a linked list in O(n log n) time using constant space complexity.
归并排序（Merge Sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
归并操作(Merge)，也叫归并算法，指的是将两个已经排序的序列合并成一个序列的操作。归并排序算法依赖归并操作。归并排序有多路归并排序、两路归并排序 , 可用于内排序，也可以用于外排序。这里仅对内排序的两路归并方法进行讨论。
算法思路：
-- http://bubkoo.com/2014/01/15/sort-algorithm/merge-sort/
归并排序的复杂度：
时间复杂度：平均、最好、最坏都是O(nlog2n)
空间复杂度：辅助存储O(n)
稳定性：稳定
方法：
采用归并排序的思想。使用快慢指针找到中间节点，递归地将链表分为左右两部分，当每部分分解到只剩一个节点时，在进行合并及排序。
Java
1 /** 2 * Definition for singly-linked list. 3 * public class ListNode { 4 * int val; 5 * ListNode next; 6 * ListNode(int x) { val = x; } 7 * } 8 */ 9 class Solution { 10 public ListNode mergeSort(ListNode head1, ListNode head2) { 11 ListNode preHead = new ListNode(0); 12 ListNode curNode = preHead; 13 while(head1 != null && head2 != null) { 14 if(head1.val <= head2.val) { 15 curNode.next = head1; 16 head1 = head1.next; 17 } else { 18 curNode.next = head2; 19 head2 = head2.next; 20 } 21 curNode = curNode.next; 22 } 23 curNode.next = head1 != null ? head1 : head2; 24 return preHead.next; 25 } 26 public ListNode sortList(ListNode head) { // 找到中间节点做划分 27 if(head == null || head.next == null) { 28 return head; 29 } 30 ListNode low = head, fast = head, preLow = null; 31 while(fast != null && fast.next != null) { 32 preLow = low; 33 low = low.next; 34 fast = fast.next.next; 35 } 36 preLow.next = null; 37 ListNode head1 = sortList(head); 38 ListNode head2 = sortList(low); 39 return mergeSort(head1, head2); 40 } 41 }// 8 ms
Python
1 # Definition for singly-linked list. 2 # class ListNode(object): 3 # def __init__(self, x): 4 # self.val = x 5 # self.next = None 6 7 class Solution(object): 8 # 合并及排序 9 def merge(self, l1, l2): 10 new_head = ListNode(0) 11 p = new_head 12 cur1, cur2 = l1, l2 13 while cur1 and cur2: 14 if cur1.val <= cur2.val: 15 p.next = cur1 16 cur1 = cur1.next 17 else: 18 p.next = cur2 19 cur2 = cur2.next 20 p = p.next 21 if cur1: 22 p.next = cur1 23 elif cur2: 24 p.next = cur2 25 return new_head.next 26 27 # 找到中间结点 28 def sortList(self, head): 29 """ 30 :type head: ListNode 31 :rtype: ListNode 32 """ 33 if head == None or head.next == None: 34 return head 35 pre, low, fast = head, head, head 36 while fast and fast.next: 37 pre = low 38 low = low.next 39 fast = fast.next.next 40 pre.next = None 41 l1 = self.sortList(head) 42 l2 = self.sortList(low) 43 return self.merge(l1, l2) 44
原文：http://www.cnblogs.com/renzongxian/p/7565160.html