148. [M] Sort List

https://leetcode.com/problems/sort-list/

要在 O(nlogn) 的复杂度完成排序，必然要用折半的方法。

用递归解决，基本思想是，根据长度从中间拆成两个链表，递归对这两个链表排序，然后合并两个已经排序的链表。由于拆分过程最终会拆到长度为 1 的链表，因此排序实际上是在合并的过程中完成的。

class Solution {
    public int listLength(ListNode head) {
        int len = 0;
        while (head != null) {
            head = head.next;
            len++;
        }
        return len;
    }
    
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        
        int len = listLength(head);
        ListNode a = head;
        for (int i = 0; i < len / 2 - 1; i++) {
            head = head.next;
        }
        ListNode b = head.next;
        head.next = null;
        
        a = this.sortList(a);
        b = this.sortList(b);
        return mergeList(a, b);
    }
    
    public ListNode mergeList(ListNode a, ListNode b) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (a != null && b != null) {
            if (a.val < b.val) {
                head.next = a;
                a = a.next;
            } else {
                head.next = b;
                b = b.next;
            }
            head = head.next;
        }
        if (a != null) {
            head.next = a;
        } else {
            head.next = b;
        }
        return dummy.next;
    }
}