Start learning free

LESSON 374 OF 536 · LINKED LISTS

Reorder List in JavaScript: O(n) Time and O(1) Space

Practice O(n) Read the full explanation

You are given the head of a singly linked list. Its nodes, in order, are:

L0 -> L1 -> L2 -> ... -> Ln-2 -> Ln-1 -> Ln

Reorder the list so that it becomes:

L0 -> Ln -> L1 -> Ln-1 -> L2 -> Ln-2 -> ...

That is: the first node, then the last, then the second, then the second to last, and so on, until every node is used once.

Change only the links between the nodes: don't change the values inside them and don't create new nodes. The function returns nothing. It reorders the list in place, the list still starts at head, and the list is printed from there.

 

Example 1:

Input: head = [1,2,3,4]
Output: [1,4,2,3]
Explanation: The first node, 1, stays first. The last node, 4, comes next,
then the second node, 2, and the second to last, 3:
1->4->2->3

Example 2:

Input: head = [1,2,3,4,5]
Output: [1,5,2,4,3]
Explanation: 1 and 5 (first and last), then 2 and 4 (second and second to last).
The middle node, 3, is left over and ends the list:
1->5->2->4->3

Example 3:

Input: head = [4,8]
Output: [4,8]
Explanation: With two nodes, the last node already comes right after the first:
nothing moves.

 

Constraints:

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

Note:

Your algorithm should run in O(n) time and use O(1) extra space, where n is the number of nodes: it only re-links the nodes that are already there. Copying the nodes into an array first would take O(n) extra space.

It takes three passes over the list:

  1. Find the middle with two pointers, a slow one that moves one node at a time and a fast one that moves two, and cut the list after the middle: 1->2->3->4->5 becomes 1->2->3 and 4->5.
  2. Reverse the second half, as in Reverse Linked List: 4->5 becomes 5->4.
  3. Take nodes from the two halves in turn: 1->5->2->4->3.
STEP 1 OF 18
    Ctrl + Enter to check

    JAVASCRIPT · LINKED LISTS

    Reorder List in JavaScript, explained

    Problem overview

    The method reorderList(head) receives the first node of a singly linked list with at least one node. The nodes are L0 -> L1 -> ... -> Ln, and the list must become L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, the last, the second, the second to last, and so on. Only the links between nodes change. Values stay where they are, no new nodes are created, and nothing is returned, because the list still starts at head. The lesson provides the node type, a ListNode with val and next fields.

    The list [1, 2, 3, 4] becomes [1, 4, 2, 3], and [1, 2, 3, 4, 5] becomes [1, 5, 2, 4, 3]. The middle node, 3, is what remains at the end. With two nodes, [4, 8], nothing moves.

    Approach: split, reverse, merge

    Copying the nodes into an array would make this easy, because an array can be read from both ends, but it needs O(n) extra space. A singly linked list can only be walked forward, so the lesson rearranges the links in three passes and uses O(1) extra space.

    1. Find the middle and cut the list there. A slow pointer moves one node at a time and a fast pointer two. When the fast pointer can't go further, the slow one is at the end of the first half. 1 -> 2 -> 3 -> 4 -> 5 becomes 1 -> 2 -> 3 and 4 -> 5.
    2. Reverse the second half. 4 -> 5 becomes 5 -> 4. Now the nodes the answer needs from the back (Ln, then Ln-1) can be read from the front.
    3. Merge by alternating. Take a node from the first half, then one from the reversed second half, and repeat: 1 -> 5 -> 2 -> 4 -> 3.

    Each pass visits every node at most once, so the total time is O(n).

    Step by step

    Find the middle

    1. Create slow and fast with let and start both at head.
    2. Loop while fast.next !== null and fast.next.next !== null, so fast can always take two steps.
    3. In the loop, move slow to slow.next and fast to fast.next.next.

    The loop stops with slow on the last node of the first half: the 2nd of 4 nodes, the 3rd of 5. With an odd count the middle node stays in the first half, which is how it ends up last in the result.

    Cut and reverse the second half

    1. Store slow.next, the start of the second half, in node.
    2. Set slow.next to null. Without this cut, the first half would still lead into the second, and the merged list would loop.
    3. Create prev as null: the head of the part reversed so far, which is empty at first.
    4. While node is not null: save node.next in nextNode, point node.next at prev, move prev to node, and move node to nextNode. Saving the next node first matters, because the second line overwrites the only link to the rest of the half.

    Merge

    1. Start first at head and second at prev, the head of the reversed half.
    2. While second is not null: save first.next in nextFirst and second.next in nextSecond.
    3. Set first.next to second, then second.next to nextFirst. The node from the back now sits between two nodes from the front.
    4. Move first to nextFirst and second to nextSecond.

    The second half is never longer than the first, so when it runs out every node is placed. A node left over in the first half is already at the end.

    The solution in JavaScript

    class Solution {
    reorderList(head) {
        let slow = head;
        let fast = head;
        while (fast.next !== null && fast.next.next !== null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        let node = slow.next;
        slow.next = null;
        let prev = null;
        while (node !== null) {
            const nextNode = node.next;
            node.next = prev;
            prev = node;
            node = nextNode;
        }
        let first = head;
        let second = prev;
        while (second !== null) {
            const nextFirst = first.next;
            const nextSecond = second.next;
            first.next = second;
            second.next = nextFirst;
            first = nextFirst;
            second = nextSecond;
        }
    }
}

    The JavaScript details worth knowing:

    • No return value. The method returns undefined. It works because nodes are objects, and head refers to the same node object before and after. Changing first.next changes the node itself, not a copy.
    • !== null. Links in this list end with null (ListNode sets next to null when it isn't given one). Comparing with !== checks for exactly null without any conversion.
    • Order of the assignments. In both loops, the next node is saved in a const before a link is overwritten. Changing the order loses the rest of the list.
    • let and const. Pointers that move (slow, fast, node, prev, first, second) use let. The saved links, assigned once per round, use const.

    Complexity

    Time: O(n). Finding the middle takes about n / 2 steps of slow, reversing the second half takes about n / 2 steps, and the merge takes about n / 2 rounds.

    Space: O(1). The method uses a fixed number of pointers and creates no nodes.

    Edge cases and common mistakes

    • One node. For [7] the loop condition fails immediately, slow.next is null, the reversed half is empty, and the merge loop never runs. The list stays [7].
    • Two nodes. [4, 8] stays [4, 8]: the second half is just 8, and linking it after 4 reproduces the same list.
    • Three nodes. [1, 2, 3] becomes [1, 3, 2].
    • Even and odd lengths. [1, 2, 3, 4, 5, 6] becomes [1, 6, 2, 5, 3, 4]. For 4 nodes slow stops on the 2nd node and for 5 nodes on the 3rd, so the first half is never shorter than the second.
    • Forgetting slow.next = null. The last node of the first half still points into the second half, so the merged list contains a cycle.
    • Reversing without saving node.next. After node.next = prev the rest of the half is unreachable.
    • Using values instead of links. Writing the values into the nodes in a new order breaks the rule that only links change.

    Testing

    • [1, 2, 3, 4] gives [1, 4, 2, 3].
    • [1, 2, 3, 4, 5] gives [1, 5, 2, 4, 3].
    • [4, 8] gives [4, 8].
    • [7] gives [7].
    • [1, 2, 3] gives [1, 3, 2].
    • [1, 2, 3, 4, 5, 6] gives [1, 6, 2, 5, 3, 4].
    Keep going with JavaScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free