What is the brute force approach and complexity for Reorder List?

Collect the nodes in a vector, then link the front and back nodes alternately with time complexity O(n) and space complexity O(n).

What is the optimal approach and complexity for Reorder List?

Slow/fast to split, reverse the second half, then weave one node from each half with optimal time complexity O(n) and space complexity O(1).

How do you identify the pattern for Reorder List?

Look for key signals in the prompt: "take turns, front then back" indicates Two ends of the list are used together → split at the middle, reverse one half, then weave.; "singly linked list, changed in place" indicates The back cannot be reached in one step → find the middle with slow and fast, and reverse in place.; "do not change values" indicates Only next pointers change → relink nodes, never copy values..

Reorder List

Medium·LeetCode #143 Pro OnlyMedium

LeetCode

Problem Statement

You are given the head of a singly linked list L0 → L1 → … → Ln−1 → Ln. Rearrange it into L0 → Ln → L1 → Ln−1 → L2 → Ln−2 → … . In other words, take turns: one node from the front, then one from the back, and so on.

Relink the existing nodes. Do not change any values. The function returns nothing; the list is changed in place.

Input

head, the first node of a singly linked list with at least one node.

Output

Nothing. The list itself is rearranged.

Example 1

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

Output: [1, 4, 2, 3]

Take 1 from the front, 4 from the back, 2 from the front, then 3 from the back.

Example 2

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

Output: [1, 5, 2, 4, 3]

With an odd count, the middle node 3 is the last one taken from the front.

Constraints

• The list has between 1 and 5 × 10^4 nodes.
• 1 ≤ Node.val ≤ 1000

Pattern Recognition Clues

Recognising these key signals in the problem description immediately identifies the pattern:

“take turns, front then back”

→ Two ends of the list are used together → split at the middle, reverse one half, then weave.

“singly linked list, changed in place”

→ The back cannot be reached in one step → find the middle with slow and fast, and reverse in place.

“do not change values”

→ Only next pointers change → relink nodes, never copy values.

Approach Complexity Ladder

Brute Force — store the nodes in an array, then zip from both endsO(n)O(n)

Collect the nodes in a vector, then link the front and back nodes alternately

Optimal — find the middle, reverse the back half, then weaveO(n)O(1)

Slow/fast to split, reverse the second half, then weave one node from each half

Brute Force Intuition

An array can reach any position directly. So store every node in a vector. Then link node lo, node hi, node lo + 1, node hi − 1, and so on, moving the two indexes inward until they meet.

Recognition rule for this sub-pattern:

Split, reverse, and re-weave lists. Draw the before/after picture first.

Remember this · Linked List — Reversal

Trigger

Reverse whole / part / every k nodes, reorder, palindrome check, numbers stored as lists.

Think

Which piece do I reverse, and which nodes must I remember to reconnect afterwards?

Key question

Before reversing, who is the node just before the piece and who is just after?

Brute2Best Pro Content

Unlock Complete Visual Walkthrough & Optimal C++

The interactive animated dry-run player, optimized C++ implementation, state invariant derivations, and edge-case breakdown for this question are part of Brute2Best Pro. The anchor question of every sub-pattern is completely free.

All 440 visual dry runs & algorithms

Interactive step-by-step playback with pointer & array state transitions

52 comprehensive LLD chapters

Interactive UML diagrams, real-world stories (Food Delivery, Trading, RPG), and practice solutions

40 C++ basics labs & hardware memory models

Vtables, byte layouts, assembly insights, and multi-threading race conditions

Production-ready C++23 source code

Modern idioms, clean contracts, time/space complexity derivations, and interview takeaways

Create Free Account Log in

First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Linked List — Reversal translate into production architectures and low-level memory mechanics.

LLD Architecture