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 <= 1000The key idea in Reorder List is to rearrange the nodes of a singly linked list in a specific alternating pattern: first node, last node, second node, second-last node, and so on. A common and efficient strategy uses the two-pointer technique to first locate the middle of the linked list. Once the midpoint is identified, the second half of the list can be reversed to allow easy merging.
After reversing the second half, you merge the two halves alternately, connecting nodes from the first half and the reversed half in sequence. This avoids creating extra nodes and keeps the operation in-place. Another possible idea involves using a stack to access nodes from the end, though it requires additional space.
The optimal approach runs in O(n) time because the list is traversed a constant number of times, and it typically uses O(1) extra space when performed in-place.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers + Reverse Second Half + Merge | O(n) | O(1) |
| Stack-Based Approach | O(n) | O(n) |
NeetCode
This approach involves splitting the list into two halves, reversing the second half, and then merging the two lists alternately.
Time Complexity: O(n).
Space Complexity: O(1), as the solution modifies the list in place.
1#include <stdio.h>
2#include <stdlib.h>
3
4struct ListNode {
5 int val;
6 struct ListNode*
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.
This method involves storing the linked list nodes in an array list and then rearranging their connections to achieve the desired order.
Time Complexity: O(n).
Space Complexity: O(n) due to the array storage.
1class ListNode:
2 def __init__
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, Reorder List is a common linked list problem that can appear in technical interviews at major tech companies. It tests understanding of pointer manipulation, list reversal, and efficient in-place operations.
The optimal approach uses the two-pointer technique to find the middle of the linked list, reverses the second half, and then merges the two halves alternately. This method processes the list in linear time and performs the reordering in-place with constant extra space.
The problem primarily relies on linked list manipulation. Techniques like two pointers and list reversal are key, though a stack can also be used to access nodes from the end when implementing an alternative solution.
Reversing the second half makes it easier to interleave nodes from the start and end of the list. Without reversing, accessing the last elements repeatedly would require additional traversals or extra memory.
The Python implementation uses a list to store nodes, then reorders them by alternately connecting nodes from the front and back.