Reorder List -II

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 reorderList(head) {
    if (head == null)
        return;

    // find the middle of linked list
    // in 1->2->3->4->5->6 find 4
    let slow = head,
        fast = head;
    while (fast != null && fast.next != null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    // reverse the second part of the list
    // convert 1->2->3->4->5->6 into 1->2->3 and 6->5->4
    // reverse the second half in-place
    let prev = null,
        curr = slow;
    while (curr != null) {
        let temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
    }

    // merge two sorted linked lists
    // merge 1->2->3 and 6->5->4 into 1->6->2->5->3->4
    let first = head,
        second = prev;

    while (second.next != null) {
        let temp1 = first.next,
            temp2 = second.next;
        first.next = second;
        first = temp1;
        second.next = temp1;
        second = temp2;
    }
    return head;
}