leetcode--04. 链表排序

题目：
Sort a linked list in O(n log n) time using constant space complexity
对链表排序，要求空间复杂度为O( nlogn )

思路:
可用归并，可以用快排

public class Solution {

    public ListNode sortList(ListNode head) {

        quickSort(head, null);

        return head;

    }

    public static void quickSort(ListNode head, ListNode end) {
        if (head != end) {
            ListNode partion = partion(head);
            quickSort(head, partion);
            quickSort(partion.next, end);
        }
    }

    public static ListNode partion(ListNode head) {
        ListNode slow = head;
        ListNode fast = head.next;
        while (fast != null) {
            if (fast.val < head.val) {
                slow = slow.next;
                fast.val = slow.val ^ fast.val ^ (slow.val = fast.val);
            }
            fast = fast.next;
        }
        slow.val = head.val ^ slow.val ^ (head.val = slow.val);
        return slow;
    }
}