Reorder List -II

Given the head of a singly linked list, reorder the list as if it were folded on itself.

Given the head of a singly linked list, reorder the list as if it were folded on itself.

Statement

Given the head of a singly linked list, reorder the list as if it were folded on itself. For example, if the list is represented as follows:

L0 → L1 → L2 → … → Ln-2 → Ln-1 → Ln

This is how you'll reorder it:

L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …

You don't need to modify the values in the list's nodes; only the links between nodes need to be changed.

Examples

Example 1

Input: head = [1, 2, 3, 4]

Explanation: Folding the list: L0 = 1, L1 = 2, L2 = 3, L3 = 4. Reordered as L0 → L3 → L1 → L2 → 1 → 4 → 2 → 3.

Output: [1, 4, 2, 3]

Example 2

Input: head = [1, 2, 3, 4, 5]

Explanation: Folding the list: L0 = 1, L1 = 2, L2 = 3, L3 = 4, L4 = 5. Reordered as L0 → L4 → L1 → L3 → L2 → 1 → 5 → 2 → 4 → 3.

Output: [1, 5, 2, 4, 3]

Solution We'll find the middle node, reverse the second half and connect both of them.

function reorder(head) {
    // find mid
    let slowPointer = head;
    let fastPointer = head;
    while (fastPointer !== null && fastPointer.next !== null) {
        fastPointer = fastPointer.next.next;
        slowPointer = slowPointer.next;
    }

    // reverse second half
    let reversed = slowPointer.next;
    slowPointer.next = null;
    reversed = reverse(reversed);

    // merge first half with second half
    let ptr1 = head;
    let ptr2 = reversed;
    while (ptr1 !== null && ptr2 !== null) {
        let ptr1next = ptr1.next;
        let ptr2next = ptr2.next;
        ptr1.next = ptr2;
        ptr2.next = ptr1next;
        ptr1 = ptr1next;
        ptr2 = ptr2next;
    }

    return head;
}