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

reorderList.js

// O(n) time, O(1) space
var reorderList = function(head) {
    if(!head || !head.next) return;
    
    // split in half
    let [slow, fast, prev] = [head, head, null];
    while(fast && fast.next){
        prev = slow;
        slow = slow.next;
        fast = fast.next.next;
    }
    let backHalfHead = prev.next;
    prev.next = null;
    
    // reverse second half
    let [a, b] = [backHalfHead, backHalfHead.next];
    a.next = null;
    while(b){
        let tmp = b.next;
        b.next = a;
        a = b;
        b = tmp;
    }
    backHalfHead = a;
    
    // weave together
    [a, b] = [head, backHalfHead];
    while(a && b){
        let tmpA = a.next;
        let tmpB = b.next;
        a.next = b;
        b.next = tmpA || tmpB;
        a = tmpA;
        b = tmpB;
    }
};