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 implement a data structure that supports the following operations efficiently: get element by index, add element at head, add element at tail, add element at an arbitrary index, and delete element at an arbitrary index. Which approach best guarantees efficient average-case performance for all these operations?

easy

A. Use a dynamic array and resize it when needed to support all operations.

B. Use a balanced binary search tree keyed by index to support all operations in O(log n).

C. Use a singly linked list with sentinel head and tail pointers, maintaining the size for boundary checks.

D. Use a hash map to store index-to-node mappings for constant time access.

Solution

Solution:

1. Step 1: Understand operation requirements

   The problem requires efficient get, add at head, add at tail, add at index, and delete at index operations.

2. Step 2: Evaluate approaches

   Dynamic arrays have O(n) add/delete at head or arbitrary index due to shifting. Singly linked lists have O(1) add at head/tail but O(n) get and add/delete at arbitrary index. Balanced BSTs keyed by index can support all operations in O(log n) time, providing efficient average-case performance. Hash maps do not maintain order and cannot efficiently support index-based operations.

3. Step 3: Choose best approach

   Balanced BST keyed by index offers O(log n) for all operations, which is more efficient on average than linked list or array for arbitrary index operations.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   Balanced BST supports all required operations efficiently [OK]

Hint: Balanced BST keyed by index supports all operations in O(log n) [OK]

Common Mistakes:

• Assuming linked list provides efficient arbitrary index access
• Thinking arrays support O(1) insertions at head
• Assuming hash maps maintain order

2. What is the time complexity of the recursive approach that converts a binary number in a linked list to an integer by accumulating the value with bit shifts?

medium

A. O(n log n) due to bit shifts at each node

B. O(n^2) because recursion stack causes repeated computations

C. O(n) because each node is visited once with constant work

D. O(n) time but O(n^2) space due to recursion stack

Solution

Solution:

1. Step 1: Analyze time per node

   Each node is processed once, performing a constant number of bit operations (shift and OR).

2. Step 2: Consider recursion overhead

   Recursion depth is n, but no repeated computations occur; each call does O(1) work.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Linear traversal with constant work per node [OK]

Hint: Bit shifts are O(1) operations, not O(log n) [OK]

Common Mistakes:

• Assuming bit shifts cost O(log n)
• Confusing recursion stack space with time complexity
• Thinking recursion causes repeated work

3. 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

4. Consider the following buggy code snippet for reversing nodes in k-groups. Which line contains the subtle bug that can cause incorrect output when the list length is not a multiple of k?

medium

A. Line missing the check 'if count < k: break' after counting nodes

B. Line with 'group_next = kth.next' assignment

C. Line with 'while kth.next and count < k:' loop

D. Line with 'tmp.next = group_next' pointer update

Solution

Solution:

1. Step 1: Identify missing boundary check

   The code does not check if the remaining nodes are fewer than k before reversal.

2. Step 2: Consequence of missing check

   Without 'if count < k: break', partial groups get reversed incorrectly, breaking problem constraints.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Missing break causes partial group reversal [OK]

Hint: Always check group size before reversal [OK]

Common Mistakes:

• Forgetting to break on partial group
• Misplacing pointer updates
• Assuming kth always valid

5. Suppose the linked list design is extended to allow negative indices in get and addAtIndex operations, where -1 refers to the last element, -2 to the second last, and so forth. Which modification correctly supports this feature without degrading average operation time complexity?

hard

A. Reject negative indices as invalid to keep implementation simple and efficient.

B. Traverse from tail backwards for negative indices to achieve O(1) access.

C. Use a doubly linked list instead of singly linked list to support backward traversal efficiently.

D. Modify get and addAtIndex to convert negative indices to positive by adding size, then proceed normally.

Solution

Solution:

1. Step 1: Understand negative index semantics

   Negative indices map to positive indices by adding the list size (e.g., -1 -> size-1).

2. Step 2: Implement index normalization

   Convert negative indices to positive by adding size before performing normal operations, preserving O(n) traversal.

3. Step 3: Evaluate alternatives

   Backward traversal from tail is not possible in singly linked list; doubly linked list adds complexity and space; rejecting negatives loses functionality.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Index normalization preserves existing complexity and correctness [OK]

Hint: Normalize negative indices by adding size before operation [OK]

Common Mistakes:

• Trying backward traversal in singly linked list
• Switching to doubly linked list unnecessarily
• Ignoring negative indices