Bird
Raised Fist0
Interview Prepfast-slow-pointersmediumAmazonMicrosoftFacebook

Reorder List (L0→Ln→L1→Ln-1)

Choose your preparation mode4 modes available
📋
Problem

Imagine you have a playlist of songs and want to reorder it so that the first song is followed by the last, then the second, then the second last, and so on, creating a new listening experience.

Given the head of a singly linked list, reorder the list to follow the pattern: L0 → Ln → L1 → Ln-1 → L2 → Ln-2 → ... You must do this in-place without altering the node values, only rearranging the nodes themselves.

The number of nodes in the list is in the range [1, 10^5]Node values can be any integerYou must reorder the list in-place with O(1) extra space
Edge cases: Single node list → output same listTwo node list → output same listList with all nodes having same value → reorder still applies but output looks same
</>
IDE
def reorderList(head: Optional[ListNode]) -> None:public void reorderList(ListNode head)void reorderList(ListNode* head)function reorderList(head)
def reorderList(head):
    # Write your solution here
    pass
class Solution {
    public void reorderList(ListNode head) {
        // Write your solution here
    }
}
#include <vector>
using namespace std;

void reorderList(ListNode* head) {
    // Write your solution here
}
function reorderList(head) {
    // Write your solution here
}
0/9
Common Bugs to Avoid
Wrong: [1, 2, 3, 4]Did not reorder the list at all; missing the reordering logic.✅ Implement the full reorder logic: find middle, reverse second half, merge halves.
Wrong: [1, 3, 2, 4]Incorrect merging order; merged nodes in wrong sequence.✅ Merge nodes alternately from first half and reversed second half correctly.
Wrong: [1, 2]Incorrectly reordered two node list or returned early without checking.✅ Return early only for lists with less than two nodes; do not reorder two node lists.
Wrong: [7, 7, 7, 7, 7]Swapped node values instead of rearranging nodes.✅ Rearrange node pointers, do not swap values.
Wrong: Timeout or crashUsed O(n^2) or extra space approach causing TLE on large inputs.✅ Use O(n) time and O(1) space approach with fast/slow pointers and in-place reversal.
✓
Test Cases
t1_01basic
Input{"head":[1,2,3,4]}
Expected[1,4,2,3]

The list is reordered by taking first node 1, last node 4, second node 2, then third node 3.

t1_02basic
Input{"head":[1,2,3,4,5]}
Expected[1,5,2,4,3]

Reordered list takes first node 1, last node 5, second node 2, second last node 4, then middle node 3.

t2_01edge
Input{"head":[1]}
Expected[1]

Single node list remains unchanged after reorder.

t2_02edge
Input{"head":[1,2]}
Expected[1,2]

Two node list remains unchanged after reorder since pattern is same as original.

t2_03edge
Input{"head":[7,7,7,7,7]}
Expected[7,7,7,7,7]

All nodes have same value; reorder still applies but output looks same due to identical values.

t3_01corner
Input{"head":[1,2,3,4,5,6]}
Expected[1,6,2,5,3,4]

Even length list reordered correctly alternating from front and back halves.

t3_02corner
Input{"head":[1,2,3,4,5,6,7]}
Expected[1,7,2,6,3,5,4]

Odd length list reordered correctly with middle node last in merged order.

t3_03corner
Input{"head":[1,2,3,4,5,6,7,8]}
Expected[1,8,2,7,3,6,4,5]

Even length list reordered correctly, testing off-by-one errors in merge.

t4_01performance
Input{"head":[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32,33,34,35,36,37,38,39,40,41,42,43,44,45,46,47,48,49,50,51,52,53,54,55,56,57,58,59,60,61,62,63,64,65,66,67,68,69,70,71,72,73,74,75,76,77,78,79,80,81,82,83,84,85,86,87,88,89,90,91,92,93,94,95,96,97,98,99,100]}
⏱ Performance - must finish in 2000ms

Large input with n=100 nodes to test O(n) time complexity and in-place reorder within 2 seconds.

Practice

(1/5)
1. You need to split a singly linked list into k parts such that the sizes of the parts differ by at most one, and the order of nodes is preserved. Which approach guarantees an optimal solution with minimal passes over the list and clean code structure?
easy
A. Use a greedy approach that assigns nodes to parts until the next part would be larger, then move on.
B. Split the list by repeatedly removing the head node and appending it to parts until all nodes are distributed.
C. Precompute the total length, then split the list in-place using dummy heads and careful pointer manipulation.
D. Apply dynamic programming to decide the best split points to minimize size differences.

Solution

  1. Step 1: Understand the problem constraints

    The parts must differ in size by at most one, and the original order must be preserved.
  2. Step 2: Evaluate approaches

    Greedy and naive removal approaches do not guarantee minimal passes or clean code. Dynamic programming is unnecessary overhead. Precomputing length and using dummy heads allows a single pass split with clear structure.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Precomputing length and dummy heads -> minimal passes and clean code [OK]
Hint: Precompute length, then split in-place with dummy heads [OK]
Common Mistakes:
  • Assuming greedy splitting always works
  • Using DP unnecessarily
  • Splitting without precomputing length
2. What is the time complexity of the addAtTail operation in the optimal linked list implementation that maintains a tail pointer and size variable?
medium
A. O(n), because traversal is needed to find the tail
B. O(log n), because the list is balanced using sentinel nodes
C. O(1), because the tail pointer allows direct access to the last node
D. O(n), because updating the size requires traversal

Solution

  1. Step 1: Identify operation steps

    addAtTail uses the tail pointer to append a new node directly without traversal.
  2. Step 2: Analyze complexity

    Since tail pointer gives direct access, adding at tail is O(1). Size update is O(1) as it's a simple increment.
  3. Final Answer:

    Option C -> Option C
  4. Quick Check:

    Tail pointer eliminates traversal, so addAtTail is constant time [OK]
Hint: Tail pointer enables O(1) tail insertions [OK]
Common Mistakes:
  • Assuming traversal needed to find tail
  • Confusing size update cost
  • Thinking sentinel nodes balance list
3. What is the time complexity of the in-place iterative flattening algorithm for a multilevel doubly linked list with total n nodes, considering the worst-case scenario where each node has a child list?
medium
A. O(n) amortized, since the total number of pointer updates and traversals sums to linear over all nodes.
B. O(n) because each node is visited a constant number of times during the flattening process.
C. O(n^2) because for each node with a child, we traverse its entire child list to find the tail.
D. O(n log n) due to repeated tail searches in nested child lists.

Solution

  1. Step 1: Analyze tail-finding loop

    Although tail is found by traversing child lists, each node is visited at most once as tail or curr.
  2. Step 2: Amortized analysis

    All next pointers are traversed linearly; tail searches do not overlap nodes multiple times, so total work is linear.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Each node processed once, tail searches amortize to O(n) [OK]
Hint: Tail searches look nested but total visits are linear [OK]
Common Mistakes:
  • Assuming tail search is repeated fully for each child causing O(n^2)
  • Confusing amortized with worst-case per iteration
  • Ignoring that nodes are not revisited multiple times
4. Consider the following buggy code snippet for flattening a multilevel doubly linked list. Which line contains the subtle bug that can cause incorrect backward traversal of the flattened list?
medium
A. Line: Missing child.prev = curr assignment
B. Line: if curr.next: curr.next.prev = tail
C. Line: curr.next = child
D. Line: tail.next = curr.next

Solution

  1. Step 1: Identify pointer updates

    After connecting curr.next to child, child's prev pointer must point back to curr.
  2. Step 2: Locate missing update

    The code misses setting child.prev = curr, breaking backward links and causing incorrect prev traversal.
  3. Final Answer:

    Option A -> Option A
  4. Quick Check:

    Without child.prev update, backward traversal fails [OK]
Hint: Always update both next and prev pointers when splicing lists [OK]
Common Mistakes:
  • Forgetting to update child's prev pointer
  • Assuming tail.next update fixes all pointers
  • Confusing next and prev pointer roles
5. Suppose the problem is modified so that nodes can be reused multiple times (i.e., after reversing a group, nodes can appear again in subsequent groups). Which of the following changes to the algorithm correctly handles this scenario?
hard
A. Modify the algorithm to create new nodes for each group reversal to avoid modifying original nodes in place.
B. This problem cannot be solved by reversal; instead, use a queue to simulate repeated node usage.
C. Use recursion with memoization to store reversed groups and reuse them without modifying the original list.
D. Use the same iterative reversal approach but reset pointers to allow reusing nodes in multiple groups.

Solution

  1. Step 1: Understand node reuse implication

    Reusing nodes means original nodes must remain unchanged or duplicated to appear multiple times.
  2. Step 2: Evaluate algorithm modifications

    In-place reversal modifies nodes destructively, so creating new nodes for each group is necessary to preserve original nodes.
  3. Step 3: Assess other options

    Resetting pointers (A) breaks list integrity; recursion with memoization (C) is complex and not standard; queue simulation (B) does not solve reversal reuse.
  4. Final Answer:

    Option A -> Option A
  5. Quick Check:

    Duplicating nodes preserves original list for reuse [OK]
Hint: Node reuse requires duplication, not in-place reversal [OK]
Common Mistakes:
  • Trying to reuse nodes in place
  • Ignoring list integrity
  • Assuming recursion memoization solves reuse
Recommended

Ready to prove it?

Pass the test and this pattern moves unknown strong while earning +1 Grip toward your certificate.

10 questions~5 mineasy hard