排序链表

---

算法：排序

题目

在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序。

示例 1:

输入: 4->2->1->3
输出: 1->2->3->4
示例 2:

输入: -1->5->3->4->0
输出: -1->0->3->4->5

分析

排序算法

Java实现

使用快速排序实现：

class ListNode {
	int val;
	ListNode next;
	ListNode(int x) { val = x; }
}
class Solution {
	public ListNode sortList(ListNode head) {
		quickSort(head, null);
		return head;
	}
	public void quickSort(ListNode head, ListNode tail) {
		if (head == tail || head.next == tail) return;
		int pivot = head.val;
		ListNode left = head, cur = head.next;

		while (cur != tail) {
			if (cur.val < pivot) {
				left = left.next;
				swap(left, cur);
			}
			cur = cur.next;
		}
		swap(head, left);
		quickSort(head, left);
		quickSort(left.next, tail);
	}
	public void swap(ListNode a, ListNode b) {
		int tmp = a.val;
		a.val = b.val;
		b.val = tmp;
	}
}
public class App {
	public static int[] stringToIntegerArray(String input) {
		input = input.trim();
		input = input.substring(1, input.length() - 1);
		if (input.length() == 0) {
			return new int[0];
		}

		String[] parts = input.split(",");
		int[] output = new int[parts.length];
		for(int index = 0; index < parts.length; index++) {
			String part = parts[index].trim();
			output[index] = Integer.parseInt(part);
		}
		return output;
	}
	public static ListNode stringToListNode(String input) {
		// Generate array from the input
		int[] nodeValues = stringToIntegerArray(input);

		// Now convert that list into linked list
		ListNode dummyRoot = new ListNode(0);
		ListNode ptr = dummyRoot;
		for(int item : nodeValues) {
			ptr.next = new ListNode(item);
			ptr = ptr.next;
		}
		return dummyRoot.next;
	}
	public static String listNodeToString(ListNode node) {
		if (node == null) {
			return "[]";
		}

		String result = "";
		while (node != null) {
			result += Integer.toString(node.val) + ", ";
			node = node.next;
		}
		return "[" + result.substring(0, result.length() - 2) + "]";
	}
	public static void main(String[] args) throws IOException {
		ListNode head = stringToListNode("[8581,6131,9495,2797,105,3247,16943]");
		ListNode ret = new Solution().sortList(head);
		String out = listNodeToString(ret);
		System.out.println(out);
	}
}