见了家乡的几个小伙伴，变化还是挺大的，感慨挺多，这些都略去不谈了。自己也是有点贪玩，从除夕到初五，基本天天就是陪爸妈玩，走亲戚，见同学，K歌，打台球神马的，心都有些玩散了，今天决定正式收心，趁着回京还有几天的时间，抓紧继续补充一下算法功底，有机会看看C++语法

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

题目很容易理解，在时间复杂度为O(nlogn)的限定下，对链表进行排序

时间复杂度为O(nlogn)的排序算法也是相当有限，堆排序，快速排序，归并排序，这里最适合的就是归并排序了，思路跟数组归并排序实现类似：

1. 将链表从中间分成两部分
2. 递归的对这两部分链表进行排序
3. 合并这两部分链表

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public static ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int count, middle;

        ListNode p, left, right;

        // the length of the list
        p = head;
        count = 0;
        while (p != null) {
            count++;
            p = p.next;
        }

        // distinguish the left and right
        middle = count / 2;
        p = head;
        left = right = head;
        for (int i = 0; i < middle - 1; i++) {
            p = p.next;
        }
        right = p.next;
        p.next = null;

        // recursive
        left = sortList(left);
        right = sortList(right);

        // merge two list
        ListNode res = mergeTwoList(left, right);

        return res;
    }

    public static ListNode mergeTwoList(ListNode left, ListNode right) {
        ListNode safeNode = new ListNode(Integer.MAX_VALUE);
        ListNode p = safeNode;

        while (left != null && right != null) {
            if (left.val <= right.val) {
                p.next = left;
                left = left.next;
            } else {
                p.next = right;
                right = right.next;
            }
            p = p.next;
        }

        if (left != null) {
            p.next = left;
        }

        if (right != null) {
            p.next = right;
        }

        return safeNode.next;
    }
}