学步园

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

这题思路比较直接。按照题目要求，需要在O(N*logN)时间内完成排序，所以可以考虑的排序方法只有三个：快速排序、归并排序和堆排序。然而，快速排序要求能在常数时间内置换两个指定元素，所以需要支持O(1)时间内的随机访问，这个无法在链表上实现，所以可以排除快速排序。此外，堆排序需要O(N)的额外空间进行堆的建立，而题目要求常数的空间复杂度，所以也可以排除。如此一来，只有归并排序可以考虑了。

按照分治法原理，其实也就只用实现两个步骤，即拆分链表和合并链表，都可以通过链表实现。把一个链表拆分成两半，简单做法就是先扫描一遍获得链表长度，然后再扫描一半长度进行拆分。这样需要两次扫描，虽然时间复杂度一样。更有效的方法是使用2个快慢指针，当快指针走到头的时候，慢指针会到达第一个的子链表的尾部。合并链表很直接，因为无论是用数组还是链表，都只用顺序扫描两个序列。

	// merge the two sorted sublists
	private ListNode merge(ListNode head1, ListNode head2) {
		if (head1 == null) {
			return head2;
		} else if (head2 == null) {
			return head1;
		}

		ListNode head, prev;
		if (head1.val < head2.val) {
			head = head1;
			head1 = head1.next;
		} else {
			head = head2;
			head2 = head2.next;
		}
		prev = head;

		while (head1 != null && head2 != null) {
			if (head1.val < head2.val) {
				prev.next = head1;
				head1 = head1.next;
			} else {
				prev.next = head2;
				head2 = head2.next;
			}
			prev = prev.next;
		}

		if (head1 != null) {
			prev.next = head1;
		} else if (head2 != null) {
			prev.next = head2;
		}

		return head;
	}

	public ListNode sortList(ListNode head) {
		ListNode head1, head2; // sublist heads

		// split the list into two sublists
		if (head == null || head.next == null) {
			return head;
		} else {
			ListNode fastNode = head.next, slowNode = head;
			while (fastNode != null) {
				fastNode = fastNode.next;
				if (fastNode != null) {
					fastNode = fastNode.next;
					slowNode = slowNode.next;
				}
			}

			head1 = head;
			head2 = slowNode.next;
			slowNode.next = null;
		}

		// sort the two sublists recursively
		head1 = sortList(head1);
		head2 = sortList(head2);

		return merge(head1, head2);
	}

其实我本来想把拆分链表这一步也用一个函数封装的，不过这样的话要求对两个子链表的表头地址传引用，在Java里不好实现，不过可以在C++代码里引入二级指针或者对节点地址传引用实现。