[LeetCode] #148 Sort List

/**
 * Definition for singly-linked list.
 * function ListNode(val) {
 *     this.val = val;
 *     this.next = null;
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var sortList = function(head) {
    if (head == null) {
        return head;
    }
    return mergeSort(head);
};

var mergeSort = function(head) {
    var pre_mid = findMiddle(head);
    var mid = pre_mid.next;
    
    if (mid != null && mid.next != null) {
        mid = mergeSort(mid);
    }
    pre_mid.next = null;
    if (pre_mid != head) {
        head = mergeSort(head);
    }
    return merge(head, mid);
};

var merge = function(head1, head2) {
    var dummy = new ListNode(-1);
    var cur = dummy;
    while (head1 != null && head2 != null) {
        if (head1.val <= head2.val) {
            cur.next = head1;
            head1 = head1.next;
        } else {
            cur.next = head2;
            head2 = head2.next;
        }
        cur = cur.next;
    }
    if (head1 != null) {
        cur.next = head1;
    }
    if (head2 != null) {
        cur.next = head2;
    }
    return dummy.next;
};

var findMiddle = function(head) {
    var fast = head.next;
    var slow = head;
    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }
    return slow;
};