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

sortList.js

/**
 * 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 || !head.next) return head;
    
    // now any list is of size > 1
    const midNode = midPointNode(head); // TBI. Returns the middle node in the list
    const right = midNode.next;
    midNode.next = null;
    
    const leftSorted = sortList(head);
    const rightSorted = sortList(right);
    
    // leftSorted and rightSorted are now guaranteed size 0 or 1
    return merge(leftSorted, rightSorted);
};

// private helpers
const merge = (a, b) => {
    let head, aCurr, bCurr;
    if(a.val < b.val){
        head = a;
        aCurr = a.next;
        bCurr = b;
    }else{
        head = b;
        aCurr = a;
        bCurr = b.next;
    }
    let listCurr = head;
    
    while(aCurr || bCurr){
        if(!aCurr){ // append b
            listCurr.next = bCurr;
            listCurr = listCurr.next;
            bCurr = bCurr.next;
        }
        else if(!bCurr){ // append a
            listCurr.next = aCurr;
            listCurr = listCurr.next;
            aCurr = aCurr.next;
        }
        else if(aCurr.val < bCurr.val){ // append a
            listCurr.next = aCurr;
            listCurr = listCurr.next;
            aCurr = aCurr.next;
        }
        else{ // append b
            listCurr.next = bCurr;
            listCurr = listCurr.next;
            bCurr = bCurr.next;
        }
    }
    return head;
};

const midPointNode = (node) => {
    let [slow, fast] = [node, node.next];
    
    while(fast.next && fast.next.next){
        slow = slow.next;
        fast = fast.next.next;
    }
    
    return slow;
};