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 are given a singly linked list and need to determine the length of a cycle if one exists. Which approach guarantees an optimal solution with O(n) time and O(1) space complexity?

easy

A. Use dynamic programming to store cycle lengths for sublists and combine results.

B. Use a hash set to store visited nodes and count cycle length upon revisiting a node.

C. Use two pointers moving at different speeds to detect the cycle and then count its length by traversing the cycle once.

D. Use a recursive depth-first search to detect cycles and count their lengths.

Solution

1. Step 1: Understand the problem constraints

   The problem requires detecting a cycle and counting its length efficiently in a linked list.

2. Step 2: Evaluate approaches for time and space complexity

   Using two pointers (fast and slow) allows cycle detection in O(n) time and O(1) space, then counting the cycle length by traversing the cycle once is optimal.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Fast-slow pointer approach is classic for cycle detection with constant space [OK]

Hint: Fast-slow pointers detect cycles in O(1) space [OK]

Common Mistakes:

• Believing hash sets are optimal due to extra space
• Confusing DP with cycle detection
• Using recursion unnecessarily

2. Given the following code for checking if a linked list is a palindrome, what is the final return value when the input list is 1 -> 2 -> 1?

easy

A. Infinite loop

B. False

C. True

D. Raises an exception due to null pointer

Solution

1. Step 1: Trace fast and slow pointers

   For list 1 -> 2 -> 1, slow ends at node with value 2, fast reaches end.

2. Step 2: Reverse second half and compare

   Second half starting at 2 -> 1 is reversed to 1 -> 2. Compare nodes: 1==1, 2==2, all match, so return True.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Palindrome list returns True after correct reversal and comparison [OK]

Hint: Check pointer movement and reversed half comparison carefully [OK]

Common Mistakes:

• Misplacing slow pointer causing wrong half reversal
• Off-by-one error in comparison loop
• Forgetting to advance second_half_start pointer

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

5. Suppose the problem is modified so that the linked list nodes can be reused multiple times in different parts (i.e., parts can share nodes). Which of the following changes to the original splitting algorithm correctly adapts to this new requirement?

hard

A. Split the list into k parts by creating new linked lists from scratch for each part, ignoring original links.

B. Keep the original algorithm but duplicate nodes when assigning to parts to avoid shared references.

C. Remove the step that breaks the link (current.next = null) after each part, allowing parts to share nodes.

D. Use a greedy approach assigning nodes to parts without precomputing sizes, since reuse allows overlap.

Solution

1. Step 1: Understand reuse requirement

   Nodes can appear in multiple parts, so links should not be broken to preserve shared nodes.

2. Step 2: Adapt algorithm

   Removing the link-breaking step allows parts to share nodes as required.

3. Step 3: Evaluate other options

   Duplicating nodes or creating new lists is unnecessary and inefficient; greedy without sizes breaks constraints.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Not breaking links enables node reuse [OK]

Hint: Remove link breaks to allow node reuse [OK]

Common Mistakes:

• Duplicating nodes unnecessarily
• Breaking links despite reuse
• Ignoring size constraints