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

📋

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
}

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

Focus on handling small and boundary cases like single or two node lists.

Watch out for off-by-one errors and ensure you reverse the second half before merging.

Optimize your solution to O(n) time and O(1) space to handle large inputs efficiently.

t1_01basic

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

Expected[1,4,2,3]

⏱ Performance - must finish in 2000ms

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

💡 Try finding the middle of the list using fast and slow pointers.

💡 Reverse the second half of the list and then merge the two halves alternately.

💡 Split the list at middle, reverse second half, then merge nodes alternately to reorder.

Why it failed: Output incorrect - likely did not reverse second half or merge halves properly. Fix by reversing second half and merging nodes alternately.

✓ Correct reorder achieved by splitting, reversing second half, and merging alternately.

t1_02basic

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

Expected[1,5,2,4,3]

⏱ Performance - must finish in 2000ms

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

💡 Use fast and slow pointers to find the middle node.

💡 Reverse the second half starting from middle.next and set middle.next to null.

💡 Merge nodes from first half and reversed second half alternately to reorder.

Why it failed: Output incorrect - likely failed to handle odd length list middle node correctly. Fix by properly splitting at middle and merging.

✓ Correct reorder for odd length list by splitting, reversing second half, and merging.

t2_01edge

Input{"head":[1]}

Expected[1]

⏱ Performance - must finish in 2000ms

Single node list remains unchanged after reorder.

💡 Check if list has zero or one node; no reorder needed.

💡 If head is null or head.next is null, return immediately.

💡 Add a base case to return early for lists with less than two nodes.

Why it failed: Output incorrect - likely did not handle single node base case. Fix by returning immediately if list length < 2.

✓ Correctly handles single node list by no operation.

t2_02edge

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

Expected[1,2]

⏱ Performance - must finish in 2000ms

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

💡 Check if list length is two; reorder should not change order.

💡 Ensure your code does not break or reorder unnecessarily for two nodes.

💡 Return early or handle two node case explicitly to avoid incorrect reordering.

Why it failed: Output incorrect - likely reordered two node list incorrectly. Fix by returning early if list length is two.

✓ Correctly handles two node list by no reorder.

t2_03edge

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

Expected[7,7,7,7,7]

⏱ Performance - must finish in 2000ms

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

💡 Do not rely on node values to reorder; reorder nodes by position.

💡 Use pointers to rearrange nodes, not values.

💡 Ensure you reorder nodes by changing next pointers, not swapping values.

Why it failed: Output incorrect - likely swapped values instead of rearranging nodes. Fix by rearranging node pointers, not values.

✓ Correctly reorders nodes by pointers even if values are identical.

t3_01corner

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

Expected[1,6,2,5,3,4]

⏱ Performance - must finish in 2000ms

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

💡 Check that you find the exact middle node for even length lists.

💡 Ensure second half reversal starts at middle.next and middle.next is set to null.

💡 Merge two halves alternately without skipping or duplicating nodes.

Why it failed: Output incorrect - likely off-by-one error in finding middle or merging halves. Fix by correctly splitting list at middle and merging all nodes.

✓ Correctly handles even length list with proper middle split and merge.

t3_02corner

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

Expected[1,7,2,6,3,5,4]

⏱ Performance - must finish in 2000ms

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

💡 Avoid greedy approach that merges nodes without reversing second half.

💡 Use fast and slow pointers to find middle, reverse second half, then merge.

💡 Do not just alternate nodes from start and end without reversing second half.

Why it failed: Output incorrect - likely greedy approach failed to reverse second half. Fix by reversing second half before merging.

✓ Correctly reorders odd length list by reversing second half and merging.

t3_03corner

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

Expected[1,8,2,7,3,6,4,5]

⏱ Performance - must finish in 2000ms

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

💡 Check that merge loop terminates correctly when one half is exhausted.

💡 Ensure last node's next pointer is set to null to avoid cycles.

💡 After merging, set tail.next = null to terminate list properly.

Why it failed: Output incorrect - likely missing tail.next = null causing cycle or extra nodes. Fix by setting tail.next = null after merge.

✓ Correctly terminates reordered list with tail.next = null.

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]}

Expectednull

⏱ Performance - must finish in 2000ms

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

💡 Use fast and slow pointers to find middle in O(n).

💡 Reverse second half in O(n) time.

💡 Merge two halves in O(n) time to achieve overall O(n) complexity.

Why it failed: TLE error - likely using O(n^2) or extra space approach. Fix by using O(n) time and O(1) space approach with fast/slow pointers and in-place reversal.

✓ Efficient O(n) time and O(1) space reorder confirmed.

Practice

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 amortized time complexity of the visit, back, and forward operations in the two stacks approach for browser history, assuming n total operations?

medium

A. O(1) amortized per operation since each URL is pushed and popped at most once per stack

B. O(n) total for all operations combined, but O(1) worst-case per operation

C. O(log n) per operation due to stack resizing costs

D. O(n) per operation because each visit may clear the forward stack

Solution

1. Step 1: Analyze push/pop operations per URL

   Each URL is pushed once onto back_stack and popped at most once to forward_stack, and vice versa.

2. Step 2: Calculate amortized cost

   Since each URL moves between stacks a limited number of times, total operations over n steps average to O(1) per operation.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Amortized O(1) is standard for two stacks navigation [OK]

Hint: Each URL moves between stacks only a few times [OK]

Common Mistakes:

• Assuming clearing forward stack is O(n) per visit
• Confusing amortized with worst-case
• Ignoring stack push/pop costs

3. What is the time and space complexity of the optimal in-place odd-even linked list rearrangement algorithm for a list of length n?

medium

A. Time: O(n), Space: O(1) because each node is visited once and rearranged in-place

B. Time: O(n log n), Space: O(1) due to sorting nodes by index parity

C. Time: O(n), Space: O(n) due to auxiliary lists for odd and even nodes

D. Time: O(n^2), Space: O(1) because of nested pointer updates

Solution

1. Step 1: Identify loop iterations

   The while loop advances even and odd pointers through the list, each node visited once -> O(n) time.

2. Step 2: Analyze space usage

   No extra data structures are created; rearrangement is done by pointer manipulation -> O(1) space.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Linear time and constant space is standard for in-place linked list rearrangement [OK]

Hint: One pass with two pointers -> O(n) time, no extra lists -> O(1) space [OK]

Common Mistakes:

• Assuming nested loops cause O(n^2) time
• Confusing auxiliary space with recursion stack

4. What is the time complexity of the optimal iterative approach that reverses a linked list in groups of k nodes, and why?

medium

A. O(nk), because each group reversal takes O(k) and there are n/k groups.

B. O(n), because each node is visited and reversed exactly once.

C. O(n log k), because reversing each group involves log k steps due to pointer updates.

D. O(n + k), because the algorithm traverses the list plus reverses k nodes.

Solution

1. Step 1: Analyze group reversal cost

   Each group of k nodes is reversed in O(k) time.

2. Step 2: Count total groups and total nodes processed

   There are approximately n/k groups, so total time is O(k * n/k) = O(n).

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Each node is processed once during reversal [OK]

Hint: Total nodes processed once -> O(n) time [OK]

Common Mistakes:

• Multiplying n by k incorrectly
• Assuming log k factor in reversal
• Ignoring that groups partition the list

5. Identify the bug in the following code snippet for splitting a linked list into k parts:

medium

A. Line where curr is advanced without checking if curr is None, causing AttributeError.

B. Line where tails[i].next is set to curr without checking if curr is None.

C. Line where tails[i].next is set to None, which breaks the list prematurely.

D. Line where dummy_heads are created, which wastes extra space.

Solution

1. Step 1: Analyze pointer advancement

   Inside the inner loop, curr is advanced with curr = curr.next without checking if curr is None.

2. Step 2: Identify potential error

   If curr is None, accessing curr.next raises AttributeError. The check must happen before advancing curr.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing None check before curr = curr.next causes runtime error [OK]

Hint: Always check curr is not None before accessing curr.next [OK]

Common Mistakes:

• Forgetting None check before pointer advance
• Incorrectly cutting list by setting next to None too early
• Misusing dummy heads