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. Consider the following code snippet for detecting and returning the length of a cycle in a linked list. Given the linked list: 3 -> 2 -> 0 -> -4 -> (back to node with value 2), what is the returned cycle length?

easy

A. 2

B. 3

C. 4

D. 0

Solution

1. Step 1: Trace fast and slow pointers until they meet

   Slow moves 1 step, fast moves 2 steps. They meet at node with value 2 after some iterations.

2. Step 2: Count cycle length by moving slow pointer until it meets fast again

   Starting from node 2, slow moves through nodes 0, -4, then back to 2, counting 3 nodes total.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Cycle length is nodes 2 -> 0 -> -4 -> back to 2 = 3 [OK]

Hint: Cycle length equals number of unique nodes in loop [OK]

Common Mistakes:

• Off-by-one counting cycle length
• Confusing meeting point with cycle start
• Returning 0 when cycle exists

2. Consider the following buggy code snippet for detecting a circular array loop. Which line contains the subtle bug that causes incorrect detection of single-element loops as valid cycles?

medium

A. Line with 'if nums[i] == 0: continue' - skipping zeros prematurely

B. Line with 'if slow == fast: return True' - missing check for single-element loop

C. Line with 'direction = nums[i] > 0' - direction assignment incorrect

D. Line with 'nums[slow] = 0' - zeroing visited elements too early

Solution

1. Step 1: Identify where single-element loops are checked

   The original code breaks if slow == next_index(slow) to avoid single-element loops.

2. Step 2: Locate missing check

   The buggy code returns True immediately when slow == fast without verifying cycle length.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Missing single-element loop check causes false positives [OK]

Hint: Check cycle length before returning True to avoid single-element loops [OK]

Common Mistakes:

• Returning True immediately on pointer meet
• Ignoring direction consistency
• Incorrectly zeroing elements

3. Identify the bug in the following code snippet for finding the duplicate number using Floyd's cycle detection:

medium

A. The initialization of slow and fast pointers is incorrect

B. The second while loop incorrectly updates fast pointer

C. The first while loop condition causes an infinite loop

D. The return statement should return fast instead of slow

Solution

1. Step 1: Examine the first while loop condition

   The loop condition is while slow != fast, but slow and fast are initialized to the same value, so the loop never runs, causing no intersection point found.

2. Step 2: Understand consequences

   Without the loop running, slow and fast pointers do not move, so the algorithm fails to detect the cycle and returns incorrect result or loops infinitely if code is modified.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Loop condition must allow first iteration; using while True with break is correct [OK]

Hint: First loop must run at least once to find intersection [OK]

Common Mistakes:

• Using while slow != fast before pointers move
• Incorrect pointer updates inside loops
• Returning wrong pointer at the end

4. Identify the bug in the following Python code for checking if a number is happy. The code attempts to detect cycles using recursion but lacks proper cycle detection.

def isHappy(n: int) -> bool:
    def get_next(number):
        total_sum = 0
        while number > 0:
            digit = number % 10
            total_sum += digit * digit
            number //= 10
        return total_sum

    def helper(num):
        if num == 1:
            return true
        return helper(get_next(num))

    return helper(n)

medium

A. Missing base case for cycle detection causing infinite recursion

B. Incorrect sum of squares calculation in get_next function

C. Returning helper(get_next(num)) without checking if num is 1

D. Not initializing total_sum to zero before summing digits

Solution

1. Step 1: Analyze recursion base cases

   The code only stops recursion if num == 1. It does not detect cycles, so for unhappy numbers it recurses infinitely.

2. Step 2: Identify missing cycle detection

   Without tracking visited numbers or using fast-slow pointers, the recursion never terminates for cycles, causing stack overflow.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Infinite recursion due to missing cycle detection base case [OK]

Hint: Check for cycle detection in recursion to avoid infinite loops [OK]

Common Mistakes:

• Assuming recursion stops at cycles without explicit detection

5. Suppose the problem is modified so that elements in the array can be reused multiple times in cycles (i.e., cycles can revisit indices multiple times), and the direction constraint is removed. Which of the following modifications to the algorithm correctly detects cycles under these new conditions?

hard

A. Use the original fast-slow pointer approach but ignore direction checks and cycle length > 1 condition

B. Use a visited set to track all visited indices globally and detect any repeated index during traversal

C. Modify fast-slow pointer to allow revisiting indices multiple times and remove in-place marking

D. Run DFS from each index without direction checks and detect back edges to find cycles

Solution

1. Step 1: Understand new problem constraints

   Cycles can revisit indices multiple times and direction constraint is removed, so fast-slow pointer is insufficient.

2. Step 2: Identify correct cycle detection method

   DFS with back edge detection in a graph representation correctly detects cycles without direction or length constraints.

3. Step 3: Evaluate other options

   Original fast-slow pointer fails without direction; visited set alone is insufficient for complex cycles; modifying fast-slow pointer to allow revisits breaks cycle detection logic.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   DFS with back edges is standard for cycle detection in general graphs [OK]

Hint: Without direction, use DFS and back edge detection [OK]

Common Mistakes:

• Assuming fast-slow pointer works without direction
• Ignoring multiple revisits
• Using visited set without cycle structure