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

对于O(nlogn)的排序，无非是merge sort，quick sort和heap sort。这里使用merge sort的递归解法，因为使用了递归，所以严格意义上来说利用了额外的栈空间，但是迭代解法实在是很麻烦，代码不容易懂，这里就不讨论了。

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode sortList(ListNode head) {
        if(head == null || head.next == null)
            return head;
        ListNode walker = head;
        ListNode runner = head;
        while(runner.next!=null && runner.next.next!=null)
        {
            walker = walker.next;
            runner = runner.next.next;
        }
        ListNode head2 = walker.next;
        walker.next = null;
        ListNode head1 = head;
        head1 = sortList(head1);
        head2 = sortList(head2);
        return merge(head1, head2);
    }
    
    private ListNode merge(ListNode head1, ListNode head2)
    {
        ListNode helper = new ListNode(0);
        helper.next = head1;
        ListNode pre = helper;
        while(head1!=null && head2!=null)
        {
            if(head1.val<head2.val)
            {
                head1 = head1.next;
            }
            else
            {
                ListNode next = head2.next;
                head2.next = pre.next;
                pre.next = head2;
                head2 = next;
            }
            pre = pre.next;
        }
        if(head2!=null)
        {
            pre.next = head2;
        }
        return helper.next;
    }
}