题目

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

分析

由于要求O(nlgn)的时间复杂度，自然就是归并排序、堆排序、快速排序；但是，还要求了O(1)空间复杂度。

如果递归不算空间的话，可以采用递归的归并排序。

如果使用非递归的归并排序，由于是单向链表，没法像数组那样直接指定元素位置，会导致时间复杂度达到O(n^2)。

堆排序用单向链表很困难。

快速排序由于最坏时间复杂度会是O(n^2)，不靠谱，这里使用单向链表快速排序测试，会TLE。

代码

public class SortList {
	class ListNode {
		int val;
		ListNode next;

		ListNode(int x) {
			val = x;
			next = null;
		}
	}

	public ListNode sortList(ListNode head) {
		// return mergeSort(head);

		if (head == null || head.next == null) {
			return head;
		}
		ListNode tail = head;
		while (tail.next != null) {
			tail = tail.next;
		}
		return quickSort(head, tail);
	}

	private ListNode quickSort(ListNode head, ListNode tail) {
		if (head == null || tail == null || head.equals(tail)) {
			return head;
		}

		ListNode p = head;
		ListNode q = head.next;
		ListNode pPre = head;
		while (q != null && !q.equals(tail.next)) {
			if (q.val <= head.val) {
				pPre = p;
				p = p.next;
				swap(p, q);
			}
			q = q.next;
		}
		swap(head, p);
		quickSort(head, pPre);
		quickSort(p.next, tail);

		return head;
	}

	private void swap(ListNode ln1, ListNode ln2) {
		int temp = ln1.val;
		ln1.val = ln2.val;
		ln2.val = temp;
	}

	private ListNode mergeSort(ListNode head) {
		if (head == null || head.next == null) {
			return head;
		}

		// find the mid node, and split to two lists
		ListNode p = head;
		ListNode q = head;
		ListNode pPre = p;
		while (q != null && q.next != null) {
			pPre = p;
			p = p.next;
			q = q.next.next;
		}
		pPre.next = null; // split

		// divide and conquer
		ListNode l1 = mergeSort(head);
		ListNode l2 = mergeSort(p);

		// merge
		return merge(l1, l2);
	}

	private ListNode merge(ListNode l1, ListNode l2) {
		ListNode guard = new ListNode(0); // guard
		ListNode tail = guard;
		while (l1 != null && l2 != null) {
			if (l1.val < l2.val) {
				tail.next = l1;
				l1 = l1.next;
			} else {
				tail.next = l2;
				l2 = l2.next;
			}
			tail = tail.next;
		}

		if (l1 != null) {
			tail.next = l1;
		} else {
			tail.next = l2;
		}
		return guard.next;
	}
}

LeetCode | Sort List