Reorder List

Problem

You are given the head of a singly linked-list. The list can be represented as:

L0 → L1 → … → Ln - 1 → Ln

Reorder the list to be on the following form:

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

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

 

Example 1:

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

Example 2:

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

 

Constraints:

• The number of nodes in the list is in the range [1, 5 * 104].
• 1 <= Node.val <= 1000

Solution

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {void} Do not return anything, modify head in-place instead.
 */
var reorderList = function(head) {
    // find middle of list and split into two
    let slow = head;
    let fast = head;
    while (fast?.next?.next) {
        fast = fast.next.next;
        slow = slow.next;
    }
    let head2 = slow.next; // head of list two
    let head1 = head; // head of list one
    slow.next = null; // end of list one

    // reverse second half of list
    let prev = null;
    let cur = head2;
    while (cur) {
        [cur.next, cur, prev] = [prev, cur.next, cur];
    }
    head2 = prev; // new head of list two (after reverse)

    // merge the two lists
    while (head2) {
        [head1.next, head1, head2] = [head2, head2, head1.next];
    }
};

Three steps are needed to reorder the list:

1. Split the list into two halves (first half is larger if odd number of elements).
2. Reverse the second half of the list.
3. Merge the two lists.

For example, if the list is [1, 2, 3, 4, 5], we get head1 = [1, 2, 3] and head2 = [4, 5] after step one; head1 = [1, 2, 3] and head2 = [5, 4] after step two; head = [1, 5, 2, 4, 3] after step three.