Start by splitting the list into two halves using slow and fast pointers. Reverse the second half and merge it with the first half by alternating nodes. This approach avoids value modification and directly manipulates node pointers, preventing common mistakes like losing references or mislinking nodes.
Problem Statement
You are given the head of a singly linked list. Each node contains an integer value. Your task is to reorder the nodes so that the sequence changes from the original L0 → L1 → L2 → ... → Ln to L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → .... The node values themselves cannot be altered; only the nodes' connections can be modified.
The list may contain up to 50,000 nodes, each with a value between 1 and 1000. You must handle edge cases such as lists with an odd number of nodes or very short lists. Your implementation should be efficient in both time and space while maintaining the linked-list structure intact.
Examples
Example 1
Input: See original problem statement.
Output: See original problem statement.
L0 → L1 → … → Ln - 1 → Ln
Example 2
Input: See original problem statement.
Output: See original problem statement.
L0 → Ln → L1 → Ln - 1 → L2 → Ln - 2 → …
Example 3
Input: head = [1,2,3,4]
Output: [1,4,2,3]
Example details omitted.
Constraints
- The number of nodes in the list is in the range [1, 5 * 104].
- 1 <= Node.val <= 1000
Solution Approach
Split the list into halves
Use slow and fast pointers to find the midpoint of the list. Slow moves one step at a time, fast moves two. After traversal, disconnect the first half from the second to prepare for merging.
Reverse the second half
Reverse the second half in place using iterative pointer reversal. This ensures the last nodes are accessible in correct order for interleaving with the first half.
Merge two halves alternatingly
Iteratively merge nodes from the first and reversed second halves. Carefully reassign next pointers to avoid losing nodes, achieving the L0 → Ln → L1 → Ln-1 → ... pattern.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity is O(n) because each node is visited a constant number of times during split, reverse, and merge. Space complexity is O(1) for in-place reversal and merging, though recursion or a stack can increase space usage if used.
What Interviewers Usually Probe
- Check if the candidate can split the list efficiently without extra space.
- Watch for correct in-place reversal of the second half.
- Ensure merging maintains the alternating pattern without node loss.
Common Pitfalls or Variants
Common pitfalls
- Modifying node values instead of pointers, which violates the problem constraints.
- Losing reference to the second half while splitting, leading to memory leaks.
- Incorrect merging order causing cycles or skipped nodes.
Follow-up variants
- Reorder list using recursion instead of iterative merge.
- Reorder list using a stack to store the second half for interleaving.
- Modify the pattern to L0 → Ln → L1 → Ln-1 → L2 → ... only for odd-length lists.
How GhostInterview Helps
- GhostInterview provides step-by-step pointer visualization to prevent losing node references.
- It highlights edge cases like short or odd-length lists to ensure robust solutions.
- It guides through optimal split, reverse, and merge operations for in-place efficiency.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
Can I change node values instead of pointers in Reorder List?
No, the problem requires manipulating the actual nodes. Altering values violates constraints and won't be accepted.
What is the easiest way to find the midpoint of a singly linked list?
Use slow and fast pointers: slow moves one node at a time, fast moves two. When fast reaches the end, slow is at midpoint.
Do I need extra space to reorder the list?
An in-place solution requires O(1) extra space, but using a stack or recursion will increase space usage.
How do I merge two halves without losing nodes?
Always store next references before reassigning pointers, and alternate nodes from each half until all nodes are merged.
Is Reorder List considered a Linked-list pointer manipulation pattern?
Yes, the core challenge is rearranging pointers without changing node values, which exemplifies the linked-list pointer manipulation pattern.
Need direct help with Reorder List instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Reorder List from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve Palindrome Linked List by finding the midpoint, reversing the second half, and comparing mirrored nodes in linear time.
Open problem page#142 Linked List Cycle IIIdentify the start of a cycle in a linked list using pointer manipulation, efficiently handling edge cases without modifying the list.
Open problem page#141 Linked List CycleDetermine if a given linked list contains a cycle using pointer manipulation or hashing, focusing on detecting repeated nodes efficiently.
Open problem page