归档 2014年11月21日

题目描述：

Sort a linked list in O(n log n) time using constant space complexity.

题目大意：

使用常数空间复杂度，对一个链表执行O(n log n）时间复杂度的排序

解题思路：

归并排序，链表的中点可以通过“快慢指针”法求得。

Python代码：

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self ...

由于链表（LinkedList）不支持随机访问（Random Access），只允许顺序访问，因此对于链表的O(logn)时间复杂度的排序算法不可以采用诸如快速排序等基于随机访问的排序算法，而归并排序可以满足这一需求。

归并排序是分治法（Divide and Conquer）的典型应用，其伪代码如下：

merge_sort(list) {
  split list into two halfs, say first and second ;
  merge_sort(firstHalf);
  merge_sort(secondHalf);
  merge(firstHalf,secondHalf);
}

下面的Java代码实现了对单链表（singly linked list）的归并排序，代码实现优美 ...