Start learning free

LESSON 378 OF 540 · LINKED LISTS

Reorder List in TypeScript: Middle, Reverse and Merge in 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

    TYPESCRIPT · LINKED LISTS

    Reorder List in TypeScript, explained

    Problem overview

    The method reorderList(head) receives the first node of a singly linked list with at least one node. The list is L0 -> L1 -> ... -> Ln, and it must be rearranged, in place, into L0 -> Ln -> L1 -> Ln-1 -> L2 -> ...: the first node, then the last, then the second, then the second to last, and so on. Only the links may change. The values stay where they are, no new nodes are created, and the method returns nothing, because the list still starts at head. The lesson provides the ListNode type, whose nodes have a val and a next that is a node or null.

    For 1->2->3->4 the result is 1->4->2->3. For 1->2->3->4->5 it is 1->5->2->4->3, where the middle node 3 is left over and ends the list. With two nodes, 4->8, nothing moves.

    Approach: three passes over the list

    A singly linked list can only be walked forwards, so reaching the last node, then the second to last, is not directly possible. Copying the nodes into an array would solve that, but it costs O(n) extra space. The in-place idea splits the problem into three smaller ones:

    1. Find the middle and cut the list there. 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 from the back of the list can be walked from the front.
    3. Merge the halves, alternating. Take a node from the first half, then one from the reversed second half: 1->5->2->4->3.

    Each pass is linear and uses only a few pointers.

    Step by step

    Pass 1: the middle

    1. Two pointers. Create slow and fast with let, both set to head.
    2. Loop while fast.next !== null && fast.next.next !== null, that is, while fast has two more nodes ahead.
    3. Move slow one node and fast two nodes. When the loop stops, slow is on the last node of the first half. For four nodes it ends on the second node, and for five on the third.
    4. Remember the second half: let node = slow.next.
    5. Cut: set slow.next = null. Without the cut, the first half would still point into the second, and the finished list would loop back on itself.

    Pass 2: reverse the second half

    1. Start with an empty reversed part: let prev: ListNode | null = null. The type annotation says that prev will hold nodes later.
    2. Loop while node !== null. Each round turns one node around.
    3. Save the next node in nextNode before changing node.next, or the rest of the half would be lost.
    4. Point node.next back at prev. This is the reversal.
    5. Advance: prev = node, then node = nextNode.

    Pass 3: merge

    1. Two walkers: first starts at head, and second at prev, the head of the reversed half.
    2. Loop while second !== null. The second half is never longer than the first, so when it runs out every node is placed. A leftover node in the first half is already at the end.
    3. Save where each half continues: nextFirst and nextSecond.
    4. Link first.next = second, then second.next = nextFirst: the back node now sits between two front nodes.
    5. Move on: first = nextFirst and second = nextSecond.

    The solution in TypeScript

    class Solution {
    reorderList(head: ListNode | null): void {
        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: ListNode | null = 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;
        }
    }
}

    Details worth knowing:

    • The return type void. The method changes the nodes it is given, and the caller keeps using head, which is still the first node. There is nothing to return.
    • ListNode | null and the compiler. The parameter is typed as possibly null, yet the code writes fast.next without a check. The lesson's compiler settings are not strict about null, so this is accepted. The lesson says the list has at least one node, which is what makes it safe. With --strict, the compiler reports "possibly null" errors on those lines.
    • Types are erased. Annotations such as ListNode | null disappear when the code is compiled to JavaScript. They do not check anything while the program runs.
    • Short-circuit &&. In the loop, fast = fast.next.next is safe only because the loop condition has just checked both nodes. The order matters: && stops at the first false operand, so fast.next.next is never read when fast.next is null.
    • Order of the two assignments in the merge. first.next = second overwrites the link to the rest of the first half, which is why nextFirst was saved first.

    Complexity

    Time: O(n). Finding the middle takes about n / 2 steps, since fast moves two nodes at a time. The reversal visits the second half once, and the merge visits each node once.

    Space: O(1). The code uses a handful of pointer variables and creates no nodes, whatever the length of the list.

    Edge cases and common mistakes

    • One node. fast.next is null, so the first loop doesn't run. Then slow.next is null, so node is null, the reversal does nothing, second is null, and the list is unchanged.
    • Two nodes. 4->8 stays 4->8: the middle is the first node, the second half is just 8, and merging puts it right after 4.
    • Odd and even lengths. 1->2->3 becomes 1->3->2, and 1->2->3->4->5->6 becomes 1->6->2->5->3->4. With an odd length the first half is one node longer, and that extra node ends the list.
    • Forgetting the cut. If slow.next is not set to null, the first half keeps pointing into the second, and the result contains a cycle.
    • Losing the rest of a list. Every time a next is overwritten (in the reversal and in the merge), the old value must be saved first.

    Testing

    • [1,2,3,4] becomes 1->4->2->3.
    • [1,2,3,4,5] becomes 1->5->2->4->3.
    • [4,8] stays 4->8.
    • [7] stays 7.
    • [1,2,3] becomes 1->3->2.
    • [1,2,3,4,5,6] becomes 1->6->2->5->3->4.

    For [1,2,3,4,5], after the first pass slow is on 3 and the halves are 1->2->3 and 4->5. After the reversal the second half is 5->4.

    Keep going with TypeScript500+ step-by-step lessons, from your first line of code to coding interviews. Free to start.
    Start learning free