Skip to main content
Talentd

Reorder List - Solution & Explanation

MediumLinked ListTwo PointersStackRecursion17 min readAsked at: Amazon, Microsoft, Apple +12
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You are given the head of a singly linked list. The goal is to reorder nodes so the list follows the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 .... The structure must be modified in-place without changing node values—only pointers can be rearranged.

Approach 1: Using Array List (O(n) time, O(n) space)

This approach copies all nodes into an array-like structure so you can access both ends easily. First iterate through the linked list and push each node into an ArrayList or dynamic array. Then use two pointers: one starting at the beginning and one at the end. Alternate linking nodes from the front and back while moving the pointers inward. Because random access is O(1), the reordering becomes straightforward. The tradeoff is extra memory proportional to the number of nodes. This approach is simple to reason about and helpful when first understanding pointer rearrangement in a linked list.

Approach 2: Reverse Second Half and Merge (O(n) time, O(1) space)

This is the optimal in-place technique and the one most interviewers expect. First find the middle of the list using the classic slow and fast pointer strategy from two pointers. Once the midpoint is located, reverse the second half of the list. Now you have two lists: the original first half and a reversed second half. Finally merge them by alternating nodes—take one node from the first half, then one from the reversed half, and repeat until the lists are exhausted.

The key insight is that reversing the second half allows you to access the last nodes in forward order without using extra memory. Reversal itself runs in O(n) time and constant space by iteratively updating next pointers. During the merge phase, pointers are carefully rewired so nodes interleave correctly without losing references. This technique relies purely on pointer manipulation and avoids auxiliary structures like a stack or array.

Recommended for interviews: The reverse-and-merge approach is the expected solution because it runs in O(n) time and O(1) extra space. Interviewers often want to see if you can combine multiple linked list techniques: finding the middle, reversing a list, and merging two lists. Starting with the array approach demonstrates the core idea, but implementing the in-place method shows stronger mastery of pointer manipulation.

Approach 1: Reverse Second Half and Merge

This approach involves splitting the list into two halves, reversing the second half, and then merging the two lists alternately.

  1. Use the slow and fast pointer technique to find the middle of the list.
  2. Reverse the second half of the list.
  3. Merge the first half of the list with the reversed second half.

The C solution first finds the midpoint using two pointers, splits the list, reverses the second half, and then merges the first half with the reversed second half node by node.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n).
Space Complexity: O(1), as the solution modifies the list in place.

Try this approach in the editor →

Approach 2: Using Array List

This method involves storing the linked list nodes in an array list and then rearranging their connections to achieve the desired order.

  1. Traverse the linked list and store each node in an array list.
  2. Use two pointers from start and end of the array to relink the nodes in the desired order.

The C++ solution uses an array to store nodes and then reorganizes them using two pointers, one from the start and one from the end of the list, alternately linking them.

Code

C++JavaPython

C++

Java

Python

Complexity

Time Complexity: O(n).
Space Complexity: O(n) due to the array storage.

Try this approach in the editor →

Approach 3: Fast and Slow Pointers + Reverse List + Merge Lists

We first use fast and slow pointers to find the midpoint of the linked list, then reverse the second half of the list, and finally merge the two halves.

The time complexity is O(n), where n is the length of the linked list. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScriptC#

Python

Java

C++

Go

TypeScript

Rust

JavaScript

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Reverse Second Half and Merge

Time Complexity: O(n).
Space Complexity: O(1), as the solution modifies the list in place.

Using Array List

Time Complexity: O(n).
Space Complexity: O(n) due to the array storage.

Fast and Slow Pointers + Reverse List + Merge Lists—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Using Array ListO(n)O(n)Simpler implementation when extra memory is acceptable
Reverse Second Half and MergeO(n)O(1)Optimal interview solution with constant extra space

Video Solution

Linkedin Interview Question - Reorder List - Leetcode 143 - Python • NeetCode • 459,456 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Reorder List easy or hard?
Reorder List is generally classified as a medium difficulty problem. The challenge comes from combining multiple linked list operations—finding the midpoint, reversing a list, and merging lists—while carefully maintaining pointer references.
How to solve Reorder List in O(n)?
Find the middle of the list using slow and fast pointers, reverse the second half of the list, then merge the two halves by alternating nodes. Each phase—middle detection, reversal, and merge—takes linear time, resulting in overall O(n) complexity with O(1) extra space.
What is the best approach for Reorder List?
The best approach is reversing the second half of the linked list and then merging it with the first half. This technique uses the slow–fast pointer method to find the middle, reverses the second half in place, and alternates nodes during merge. It runs in O(n) time with O(1) extra space, which is considered the optimal solution.
What data structure is used in Reorder List?
The problem is based on a singly linked list. The optimal solution uses pointer manipulation with techniques such as the two-pointer method and in-place list reversal. Some simpler implementations also use an auxiliary array or stack to access nodes from both ends.
What is the time complexity of Reorder List?
The optimal algorithm runs in O(n) time because the list is traversed a constant number of times: once to find the middle, once to reverse the second half, and once to merge the halves. Each step is linear and does not involve nested iteration.
Reorder List Python or Java solution approach?
Python and Java solutions typically implement the reverse-second-half strategy. First locate the middle node with slow and fast pointers, reverse the remaining list iteratively, then interleave nodes from the first half and the reversed second half until the list is reordered.
Is Reorder List asked at Google, Amazon, or Meta?
Reorder List is a common medium-level linked list problem frequently asked in technical interviews. Variants of this pattern have appeared in interviews at companies like Amazon, Meta, and Google because it tests pointer manipulation and multiple linked list techniques in one problem.

Ready to solve this problem?

Practice Reorder List with our built-in code editor and test cases.

Practice on FleetCode
Previous

Delete the Middle Node of a Linked List

Next

Take K of Each Character From Left and Right