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:
[1, 5 * 104].1 <= Node.val <= 1000Problem Overview: You are given the head of a singly linked list. The list must be reordered in-place to follow the pattern L0 → Ln → L1 → Ln-1 → L2 → Ln-2 .... Only node links can change; node values cannot be modified. The challenge is restructuring the list efficiently without using excessive extra memory.
Approach 1: Using Array List (O(n) time, O(n) space)
The simplest way is to copy all nodes into a dynamic array or list. Once stored, you can access nodes from both ends using two pointers: one starting at index 0 and the other at n-1. Reconnect nodes alternately by linking the left pointer node, then the right pointer node, then moving inward. This works because arrays allow constant-time indexing, which makes picking elements from the front and back trivial. The downside is the extra O(n) memory needed to store references to every node.
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, locate the middle of the list using the classic slow/fast pointer technique from two pointers. Once the midpoint is found, split the list into two halves. Reverse the second half using standard linked list reversal.
After reversal, merge the two halves by alternating nodes. Start with the head of the first half and the head of the reversed second half. Attach one node from the first list, then one from the second, and continue until the second half is exhausted. Because the second half was reversed, nodes naturally appear in the required order Ln, Ln-1, .... This approach only modifies pointers and does not allocate extra data structures, which keeps space complexity at O(1).
The key insight is that the required order is essentially an interleaving of the first half and the reversed second half. Breaking the problem into three deterministic steps—find middle, reverse, merge—keeps the logic simple and avoids complicated pointer juggling.
Some implementations also use a stack to access nodes from the end, which conceptually mirrors the array approach but with O(n) auxiliary space. The reverse-and-merge method avoids that overhead.
Recommended for interviews: The reverse second half and merge approach is the expected solution. It demonstrates mastery of linked list manipulation, slow/fast pointers, and in-place reversal. Starting with the array-based idea shows you understand the ordering requirement, but implementing the O(n) time and O(1) space method shows stronger algorithmic skill.
This approach involves splitting the list into two halves, reversing the second half, and then merging the two lists alternately.
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.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n).
Space Complexity: O(1), as the solution modifies the list in place.
This method involves storing the linked list nodes in an array list and then rearranging their connections to achieve 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.
Java
Python
Time Complexity: O(n).
Space Complexity: O(n) due to the array storage.
| Approach | Complexity |
|---|---|
| Reverse Second Half and Merge | Time Complexity: O(n). |
| Using Array List | Time Complexity: O(n). |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Using Array List | O(n) | O(n) | Simple implementation when extra memory is acceptable |
| Reverse Second Half and Merge | O(n) | O(1) | Optimal in-place solution expected in coding interviews |
Linkedin Interview Question - Reorder List - Leetcode 143 - Python • NeetCode • 345,328 views views
Watch 9 more video solutions →Practice Reorder List with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor