Leetcode - Sort List

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

[分析] 将链表二分，递归排序子链表，然后merge 已排序的两子链表。

public class Solution {
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null)
            return head;
        // split the list in a 2 pointer style
        ListNode p = head, q = head;
        while (q.next != null) {
            q = q.next;
            if (q.next != null) {
                q = q.next;
                p = p.next;
            }
        }
        // sort 2 sublists
        ListNode half1 = head, half2 = p.next;
        p.next = null;
        half1 = sortList(half1);
        half2 = sortList(half2);
        // merge 2 sublist
        ListNode dummy = new ListNode(0);
        p = dummy;
        while (half1 != null && half2 != null) {
            if (half1.val < half2.val) {
                dummy.next = half1;
                half1 = half1.next;
            } else {
                dummy.next = half2;
                half2 = half2.next;
            }
            dummy = dummy.next;
        }
        if (half1 != null) {
            dummy.next = half1;
        }
        if (half2 != null) {
            dummy.next = half2;
        }
        return p.next;
    }
}