143. Reorder List

Reorder List (LeetCode 143) is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Linked List Manipulation Patterns pattern, in the Reordering / Partitioning subpattern.

• Blind 75 · #22 of 75 · Linked List
• NeetCode 150 · #38 of 150 · Linked List
• NeetCode 250 · #77 of 250 · Linked List

How to solve Reorder List

Reorder List is a Linked List Reordering and Partitioning problem, part of Linked List Manipulation Patterns. Learn to reorder and partition linked lists. Master techniques like swap pairs, rotate list, and odd-even separation.

Work towards the solution in these steps:

1. Consider how you might divide the linked list into two parts to facilitate reordering; think about finding a midpoint in the list.
2. Explore efficient ways to find the middle node of a singly linked list, such as using two pointers moving at different speeds.
3. Once you have two halves, think about reversing the second half of the list to prepare it for merging.

The reference solution runs in O(n) time and O(n) space.

The Reorder List solution and editorial walks through the full approach with reference code.

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

Topics and companies

Topics: Linked List, Two Pointers, Stack, Recursion.

Reported in interviews at Facebook, Amazon, Splunk.

How to practise Reorder List on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(n) time and O(n) space.

Open Reorder List in the code editor, or read the Reorder List editorial for a worked solution with its approach and complexity analysis.

Where Reorder List sits in the DSA pattern sheet

• Linked List Manipulation Patterns pattern guide
• Reordering / Partitioning subpattern
• The full DSA patterns sheet

Problems related to Reorder List

Other problems that use the same Reordering / Partitioning and Linked List Manipulation Patterns techniques:

• Insert Greatest Common Divisors in Linked List — Medium, same subpattern
• Odd Even Linked List — Medium, same subpattern
• Partition List — Medium, same subpattern
• Rotate List — Medium, same subpattern
• Swap Nodes in Pairs — Medium, same subpattern
• Add Two Numbers — Medium, same pattern

Reorder List FAQ