Sort List

[kokocan12]

Problem

When a head node of Linked-List is given, sort this linked list.
This linked-list is un-ordered.

Approach

Basic concept of solution is merge sort.
Two pointers trick is used to divide to left-side, right-side.

function mergeSort(node) {
    
    if(node === null) return null;
    let slow = node;
    let fast = node;
    
    // O O
    // S
    // O-O-O
    //   S F
    // O-O-O-O
    //   S F
    // O-O-O-O-O
    //     S   F
    // O-O-O O-O-O
    //     S   F
    // O-O-O-O O-O-O-O
    //       S     F
    // O-O-O-O-O O-O-O-O-O
    //         S         F
    while(fast.next && fast.next.next) {
        slow = slow.next;
        fast = fast.next.next;
    }
    
    if(slow===node && node.next) {
        if(node.val < node.next.val) {
            return node;
        } else {
            const next = node.next;
            node.next = null;
            next.next = node;
            
            return next;
        }
    }
    
    else if(slow===node && !node.next) {
        return node;
    } 
    
    // O-O-O-O
    //   S F
    
    const temp = slow.next;
    slow.next = null;
    let leftStart = mergeSort(node);
    let rightStart = mergeSort(temp);
    
    
    return merge(leftStart, rightStart);
}

function merge(leftStart, rightStart) {
    const dummy = new ListNode(0);
    let current = dummy;
    
    while(leftStart && rightStart) {
        if(leftStart.val < rightStart.val) {
            current.next = leftStart;
            leftStart = leftStart.next;
        } else {
            current.next = rightStart;
            rightStart = rightStart.next;
        }
        current = current.next
    }
    
    if(leftStart) {
        current.next = leftStart;
    }
    
    if(rightStart) {
        current.next = rightStart;
    }
        
    
    return dummy.next;  
}