Reorder List - JS Solution

Editorial

Editorial solutions and visualizations are prepared with care, but we do not guarantee 100% accuracy or completeness. Please use your own judgment to verify results. Visucodize is not responsible for decisions made based on this content.

const SLOW = 'slow', SLOW_COLOR = 'skyblue';
const FAST = 'fast', FAST_COLOR = 'gold';
const FIRST_HALF = 'first_half', FIRST_HALF_COLOR = 'blue';
const SECOND_HALF = 'second_half', SECOND_HALF_COLOR = 'orange';
const STORED = 'stored', STORED_COLOR = 'gray';

function visMainFunction(inputArr) {
    initClassProperties();
    explanationAndColorSchemaNotifications();

    startPartialBatch();

    const head = convertInputToLinkedList(inputArr);
    const list = new VisLinkedList(head, { dataPropName: 'val' });

    // Step 1: Find the middle
    let slow = head, fast = head.next;
    let slowVM = list.makeVisManagerForNode(slow).addClass(SLOW);
    let fastVM = list.makeVisManagerForNode(fast).addClass(FAST);

    notification(`
        To locate the <b>tail of the first half</b>, move the ${makeColoredSpan('fast pointer', FAST_COLOR)} two steps at a time
        and the ${makeColoredSpan('slow pointer', SLOW_COLOR)} one step at a time. (Here, <b>fast starts at <code>head.next</code></b>.)<br><br>
        Continue while the <b>fast pointer</b> has not reached or exceeded the end (<code>fast && fast.next</code> holds).  
        When this condition fails, the ${makeColoredSpan('slow pointer', SLOW_COLOR)} will be exactly at the <b>last node of the first half</b> — 
        a rule that works correctly for both even- and odd-length lists (see the approach section for details).  
        This gives us the perfect split point for reversing and merging.
    `);

    while (fast && fast.next) {
        slowVM.removeClass(SLOW);
        slow = slow.next;
        slowVM = list.makeVisManagerForNode(slow).addClass(SLOW);

        fastVM.removeClass(FAST);
        fast = fast.next.next;
        fastVM = fast && list.makeVisManagerForNode(fast).addClass(FAST);
    }

    notification(`📍 <b>Tail of the first half found.</b> The ${makeColoredSpan('slow pointer', SLOW_COLOR)} now points to the last node of the first half.`);
    endBatch();

    // Step 2: Reverse second half
    startPartialBatch();
    notification(`✂️ Splitting into halves by severing the link after the <b>tail of the first half</b> (set <code>slow.next = null</code>).`);
    let prev = null;
    let curr = slow.next;
    slow.next = null; // split the list

    slowVM.removeClass(SLOW);
    const reverseSecondHalfList = new VisLinkedList(prev, { dataPropName: 'val' });
    notification(`
        🔄 Reversing the second half of the list, starting from the node after the <b>tail of the first half</b>.<br>
        Watch as <b>reverseSecondHalfList</b> dynamically updates to show the reversed order forming node by node.<br>
        💡 For a detailed explanation of how linked list reversal works, see the problem 
        <b>Reverse Linked List</b> (LeetCode <code>reverse-linked-list</code>) — also available as a Visucodized solution under the same ID.
    `);

    while (curr) {
        const next = curr.next;
        curr.next = prev;
        prev = curr;
        curr = next;
    }

    notification(`✅ Reversal complete — the <b>reverseSecondHalfList</b> now displays the reversed second half in its final order.`);
    endBatch();

    // Step 3: Merge two halves
    let first = head;
    let second = prev;

    reverseSecondHalfList.destroyVis();
    const mergeAnimation = new MergeAnimation(list, first, second);

    while (second) {
        startPartialBatch();
        const {
            handleBeforeSettingNextOfFirst, handleAfterSettingNextOfFirst, handleBeforeSettingNextOfSecond, handleAfterSettingNextOfSecond,
            handleBeforeAdvancingFirstAndSecond, handleAfterAdvancingFirstAndSecond
        } = mergeAnimation.advance(first, second);

        const tmp1 = first.next;
        const tmp2 = second.next;

        handleBeforeSettingNextOfFirst();
        first.next = second;
        handleAfterSettingNextOfFirst();

        handleBeforeSettingNextOfSecond();
        second.next = tmp1;
        handleAfterSettingNextOfSecond();

        handleBeforeAdvancingFirstAndSecond();
        first = tmp1;
        second = tmp2;
        handleAfterAdvancingFirstAndSecond();
        endBatch();
    }

    notification(`🏁 <b>Done!</b> The list has been reordered as required.`);
    return head;
}

class MergeAnimation {
    constructor(list, first, second) {
        startPartialBatch();
        this.list = list;
        this.firstBeforeMerge = copyLinkedList(first);
        this.secondBeforeMerge = copyLinkedList(second);
        this.firstListBeforeMerge = new VisLinkedList(this.firstBeforeMerge, { dataPropName: 'val' }).options({ label: 'firstListBeforeMerge' }).createVis();
        this.secondListBeforeMerge = new VisLinkedList(this.secondBeforeMerge, { dataPropName: 'val' }).options({ label: 'secondListBeforeMerge' }).createVis();
        this.list.makeVisManagerForNode(first).addClass(FIRST_HALF);
        this.currentOfFirstBeforeMerge = this.firstBeforeMerge;
        this.currentOfSecondBeforeMerge = this.secondBeforeMerge;

        this.currentOfFirstVM = this.firstListBeforeMerge.makeVisManagerForNode(this.currentOfFirstBeforeMerge).addClass(FIRST_HALF);
        this.currentOfSecondVM = this.secondListBeforeMerge.makeVisManagerForNode(this.currentOfSecondBeforeMerge).addClass(SECOND_HALF);

        notification(`
            🔁 <b>Starting the merge:</b> We’ll repeatedly interleave nodes from the two halves while 
            ${makeColoredSpan('second', SECOND_HALF_COLOR)} is not <code>null</code>.<br><br>
            At each step, the current node from the ${makeColoredSpan('first half', FIRST_HALF_COLOR)} 
            is already in place. The current node from the ${makeColoredSpan('reversed second half', SECOND_HALF_COLOR)} 
            is inserted immediately after it, then we advance both pointers using the temporarily stored <code>next</code> references.<br><br>
            In an <b>even-length</b> list, both halves will finish at the same time.  
            In an <b>odd-length</b> list, one extra node from the ${makeColoredSpan('first half', FIRST_HALF_COLOR)} 
            naturally remains at the end — that’s expected and correct.
        `);
        endBatch();
    }

    advance(first, second) {
        const tmp1 = first.next;
        const tmp2 = second.next;

        const tmp1VisManager = tmp1 && this.firstListBeforeMerge.makeVisManagerForNode(this.currentOfFirstBeforeMerge.next).addClass(STORED);
        const tmp2VisManager = tmp2 && this.secondListBeforeMerge.makeVisManagerForNode(this.currentOfSecondBeforeMerge.next).addClass(STORED);
        notification(`📦 Temporarily storing the <b>next</b> pointers of both nodes (highlighted in ${makeColoredSpan(STORED_COLOR, STORED_COLOR)}) before modifying links. This ensures we retain access to the remaining nodes.`);

        const handleBeforeSettingNextOfFirst = () => notification(`🔗 Linking: setting <b>first.next</b> to point to the current second node.`);
        // first.next = second;
        const handleAfterSettingNextOfFirst = () => this.list.makeVisManagerForNode(second).addClass(SECOND_HALF);

        const handleBeforeSettingNextOfSecond = () => notification(`🔗 Then linking <b>second.next</b> to the previously stored <b>first.next</b> reference.`);
        // second.next = tmp1;
        const handleAfterSettingNextOfSecond = () => tmp1 && this.list.makeVisManagerForNode(tmp1).addClass(FIRST_HALF);


        // notification(`➡️ Advancing both first and second pointers to their stored next nodes to continue merging.`);
        const handleBeforeAdvancingFirstAndSecond = () => notification(`➡️ Advancing both first and second pointers to their stored next nodes to continue merging.`);
        // first = tmp1;
        // second = tmp2;

        const handleAfterAdvancingFirstAndSecond = () => {
            this.currentOfFirstVM.removeClass(FIRST_HALF);
            this.currentOfSecondVM.removeClass(SECOND_HALF);

            this.currentOfFirstVM = tmp1VisManager?.removeClass(STORED).addClass(FIRST_HALF);
            this.currentOfSecondVM = tmp2VisManager?.removeClass(STORED).addClass(SECOND_HALF);

            this.currentOfFirstBeforeMerge = this.currentOfFirstBeforeMerge.next;
            this.currentOfSecondBeforeMerge = this.currentOfSecondBeforeMerge.next;
        };

        return {
            handleBeforeSettingNextOfFirst, handleAfterSettingNextOfFirst, handleBeforeSettingNextOfSecond, handleAfterSettingNextOfSecond,
            handleBeforeAdvancingFirstAndSecond, handleAfterAdvancingFirstAndSecond
        }
    } 
}

function initClassProperties() {
    setClassProperties(SLOW, { backgroundColor: SLOW_COLOR });
    setClassProperties(FAST, { borderColor: FAST_COLOR });
    setClassProperties(FIRST_HALF, { backgroundColor: FIRST_HALF_COLOR });
    setClassProperties(SECOND_HALF, { backgroundColor: SECOND_HALF_COLOR });
    setClassProperties(STORED, { backgroundColor: STORED_COLOR });
}

function convertInputToLinkedList(arr) {
    const dummy = new ListNode(0);
    let current = dummy;
    for (const val of arr) {
        current.next = new ListNode(val);
        current = current.next;
    }
    return dummy.next;
}

function ListNode(val, next) {
    this.val = val === undefined ? 0 : val;
    this.next = next === undefined ? null : next;
}

function copyLinkedList(head) {
    if (!head) return null;

    const dummy = {};
    let current = head;
    let copyCurrent = dummy;

    while (current) {
        const newNode = { val: current.val, next: null };
        copyCurrent.next = newNode;
        copyCurrent = newNode;
        current = current.next;
    }

    return dummy.next;
}

function explanationAndColorSchemaNotifications() {
    explanationNotification();
    notification(`
        🎨 <b>Visual Cues:</b>
        <ul>
            <li>${makeColoredSpan('Gold border', FAST_COLOR)} → <b>fast</b> pointer</li>
            <li>${makeColoredSpan('Skyblue background', SLOW_COLOR)} → <b>slow</b> pointer</li>
            <li>${makeColoredSpan('Blue background', FIRST_HALF_COLOR)} → nodes in the <b>first half</b></li>
            <li>${makeColoredSpan('Orange background', SECOND_HALF_COLOR)} → nodes in the <b>reversed second half</b></li>
            <li>${makeColoredSpan('Gray background', STORED_COLOR)} → <b>temporarily stored</b> next pointers during merge</li>
        </ul>
        <i>Note:</i> Nodes shown <b>without background color</b> in the merged list have not yet been placed
        into their final positions — they are displayed temporarily after the most recently linked node
        from either half until the merge proceeds further.
    `);
}

Approach

Step 0: Understand the intuition behind the approach.
The target pattern is L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... Recognize that this is a reordering where we alternately take one node from the beginning and one from the end of the list, gradually moving inward from both sides.

For lists with an odd number of nodes, the single middle node naturally becomes the last node in the reordered sequence after all end-pairs are consumed. We ensure this by keeping the middle node in the first half.

To access “end” nodes in forward order, we reverse the second half so it can be traversed from what was the tail toward the middle. Once reversed, the second half provides nodes in exactly the order needed to alternate with the first half, all done in-place.
Step 1: Define the two halves.
We conceptually split the list into:
- Even length: halves of equal size.
- Odd length: the first half has one extra node (the middle), which will be the final node after reordering.
Step 2: Find the tail of the first half (split point).
Use two pointers, but initialize them with a deliberate offset to control where the split lands: the fast pointer starts at head.next and moves two steps at a time, while the slow pointer starts at head and moves one step at a time.

Continue while fast and fast.next both exist — meaning the fast pointer has not yet reached or exceeded the end. When this condition fails, the slow pointer will be positioned exactly at the tail of the first half, which serves as the perfect split point for reversing and merging later:
- Even length: slow stops at the end of the left half.
- Odd length: slow stops on the middle node (kept in the first half), which guarantees it becomes the last node after merging.
Step 3: Reverse the second half.
Sever the list after the first-half tail (slow.next = null) and reverse the remaining nodes. This makes the original tail the head of the reversed second half so we can traverse those “end” elements forward during merge.
Step 4: Merge the halves by alternating nodes.
Interleave nodes from both halves while second !== null: take one from the first half, then one from the reversed second half, and repeat. Before each relink, temporarily store each pointer’s next so you don’t lose access to the remainder of either list.
- Even length: both halves exhaust at the same time — they become null together, yielding a perfect alternation.
- Odd length: second becomes null first; the extra node in the first half (the middle) is already in place and naturally remains as the final node.
After linking first.next to the current second and second.next to the previously stored first.next, advance both pointers by assigning the stored next references.
Step 5: Why this works.
Reversing the second half converts “take from the end” into a simple forward traversal. Alternating links between the unchanged first half and the reversed second half weaves the list from the outside in, achieving the target pattern with only pointer updates and no extra storage.
Step 6: Result.
The head now points to the reordered sequence L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → …, built entirely in-place.

Time Complexity

O(n) — a linear scan to find the split, a linear scan over the second half to reverse it, and a linear scan to merge.

Space Complexity

O(1) — the algorithm reuses the same nodes and simply rewires their next pointers in place, without allocating any additional list structures.

Input-1

Reorder List - JS Solution

Solution code

Solution explanation

Solution explanation

Approach

Time Complexity

Space Complexity