Problem

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

Example

Given 1-3->2->null, sort it to 1->2->3->null.

Note

这道题目可以用分治法来做，首先从链表中点分割链表，然后将两个链表重新排序并合并。

Solution

public class Solution {
    public ListNode sortList(ListNode head) {  
        if (head == null || head.next == null) return head;
        ListNode mid = findMid(head);
        ListNode n2 = sortList(mid.next);
        mid.next = null;
        ListNode n1 = sortList(head);
        return merge(n1, n2);
    }
    public ListNode findMid(ListNode head) {
        ListNode slow = head, fast = head.next;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
    public ListNode merge(ListNode n1, ListNode n2) {
        ListNode dummy = new ListNode(0);
        ListNode head = dummy;
        while (n1 != null && n2 != null) {
            if (n1.val < n2.val) {
                head.next = n1;
                n1 = n1.next;
            }
            else {
                head.next = n2;
                n2 = n2.next;
            }
            head = head.next;
        }
        if (n1 != null) head.next = n1;
        else head.next = n2;
        return dummy.next;
    }
}