Middle of the Linked List

📋

Problem

Imagine you are reading a long scroll and want to find the exact middle point to split it evenly without counting every character.

Given the head of a singly linked list, return the middle node of the linked list. If there are two middle nodes, return the second middle node.

1 ≤ n ≤ 10^5The number of nodes in the list is at least 1Node values can be any integer

Edge cases: Single node list → return that nodeTwo node list → return second nodeAll nodes have the same value → still return second middle if even length

</>

IDE

def middleNode(head: ListNode) -> ListNode:public ListNode middleNode(ListNode head)ListNode* middleNode(ListNode* head)function middleNode(head)

def middleNode(head):
    # Write your solution here
    pass

class Solution {
    public ListNode middleNode(ListNode head) {
        // Write your solution here
        return null;
    }
}

#include <vector>
using namespace std;

ListNode* middleNode(ListNode* head) {
    // Write your solution here
    return nullptr;
}

function middleNode(head) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: 2Returning the first middle node instead of the second middle node for even length lists.✅ Return the slow pointer node after the fast pointer reaches the end, not before.

Wrong: nullNot handling single node list or empty list correctly, returning null or None.✅ Check if head is null or head.next is null and return head directly.

Wrong: 5Off-by-one error causing slow pointer to advance too far or too little.✅ Ensure slow pointer advances only after fast pointer moves two steps, and return slow when fast reaches end.

Wrong: 1Greedy approach returning first node as middle without using two pointers.✅ Use two-pointer technique to find the middle node correctly.

Wrong: 3Confusing 0-based and 1-based indexing when calculating middle node position.✅ Use integer division count//2 and advance slow pointer accordingly.

✓

Test Cases

Try testing your solution on very small lists and lists with identical values to catch base case bugs.

Consider tricky cases where the list length is even or odd and verify your pointer advancement logic.

Optimize your solution to run in a single pass using two pointers to handle large inputs efficiently.

t1_01basic

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

Expected3

⏱ Performance - must finish in 2000ms

The list has 5 nodes, so the middle is the 3rd node with value 3.

💡 Use two pointers moving at different speeds to find the middle.

💡 Move one pointer one step at a time and the other two steps at a time.

💡 When the faster pointer reaches the end, the slower pointer is at the middle node.

Why it failed: Returned wrong node value; likely did not correctly advance the slow pointer or returned the first middle in even-length list. Fix by ensuring slow pointer moves one step per iteration and fast pointer moves two steps, returning slow when fast reaches end.

✓ Correctly identified the middle node using the two-pointer technique.

t1_02basic

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

Expected4

⏱ Performance - must finish in 2000ms

The list has 6 nodes, so the middle is the 4th node with value 4 (second middle).

💡 Remember to return the second middle node when the list length is even.

💡 Use the fast pointer to detect the end of the list and slow pointer to track middle.

💡 Return the slow pointer node after fast pointer reaches null or next is null.

Why it failed: Returned first middle node instead of second for even-length list; fix by returning slow pointer after fast pointer reaches end, not before.

✓ Correctly returned the second middle node for even-length list.

t2_01edge

Input{"head":[1]}

Expected1

⏱ Performance - must finish in 2000ms

Single node list; the middle is the only node with value 1.

💡 Check behavior when list has only one node.

💡 Ensure your code handles the base case without errors.

💡 Return the head node directly if no next node exists.

Why it failed: Function failed or returned null on single node list; fix by handling base case where head.next is null and returning head.

✓ Correctly handled single node list by returning the only node.

t2_02edge

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

Expected2

⏱ Performance - must finish in 2000ms

Two node list; the middle is the second node with value 2.

💡 For even length lists, return the second middle node.

💡 Verify that your fast pointer moves two steps and slow pointer moves one step.

💡 Return slow pointer node after fast pointer reaches end.

Why it failed: Returned first node instead of second for two node list; fix by ensuring slow pointer advances correctly and returns second middle node.

✓ Correctly returned second node as middle for two node list.

t2_03edge

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

Expected7

⏱ Performance - must finish in 2000ms

All nodes have the same value 7; for even length 4, middle is the 3rd node (second middle) with value 7.

💡 Value equality does not affect middle node position.

💡 Ensure your logic returns the second middle node for even length lists.

💡 Return the slow pointer node after fast pointer reaches end.

Why it failed: Returned first middle node instead of second for even length list with identical values; fix by returning slow pointer after fast pointer reaches end.

✓ Correctly returned second middle node even when all values are identical.

t3_01corner

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

Expected6

⏱ Performance - must finish in 2000ms

Even length list of 10 nodes; middle is 6th node (second middle) with value 6.

💡 Beware of off-by-one errors in pointer advancement.

💡 Check that slow pointer moves exactly half the list length.

💡 Return slow pointer after fast pointer reaches null or next is null.

Why it failed: Returned 5th node instead of 6th due to off-by-one error; fix by ensuring slow pointer advances only after fast pointer moves two steps.

✓ Correctly handled off-by-one to return second middle node.

t3_02corner

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

Expected3

⏱ Performance - must finish in 2000ms

Odd length list; middle is 3rd node with value 3.

💡 Avoid greedy approaches that pick first middle node for even length.

💡 Use two-pointer technique to find exact middle.

💡 Return slow pointer node after fast pointer reaches end.

Why it failed: Greedy approach returned first middle node for even length lists; fix by using two-pointer method to find second middle node.

✓ Correctly avoided greedy trap and returned middle node.

t3_03corner

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

Expected4

⏱ Performance - must finish in 2000ms

Odd length list of 7 nodes; middle is 4th node with value 4.

💡 Check that your method does not confuse 0/1 indexing.

💡 Ensure slow pointer moves correctly to middle node.

💡 Return slow pointer node after fast pointer reaches end.

Why it failed: Confused 0-based vs 1-based indexing, returning wrong middle node; fix by using integer division count//2 and advancing slow pointer accordingly.

✓ Correctly handled indexing to return middle node.

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

Expectednull

⏱ Performance - must finish in 2000ms

List with 100,000 nodes; solution must run in O(n) time within 2 seconds.

💡 Use the two-pointer technique for O(n) time complexity.

💡 Avoid counting nodes twice or using extra space.

💡 Single pass with fast and slow pointers is optimal.

Why it failed: Solution timed out due to O(n^2) or multiple passes; fix by implementing single-pass two-pointer approach.

✓ Solution runs in O(n) time and passes performance test.

Practice

1. What is the time complexity of the optimized fast-slow pointer algorithm for detecting a cycle in a circular array of length n, where each element can be positive or negative steps? Assume the algorithm marks visited elements in-place to avoid repeated work.

medium

A. O(n) because each element is visited at most twice due to in-place marking

B. O(n) average but O(n^2) worst-case if cycles overlap heavily

C. O(n log n) due to repeated modulo operations and pointer jumps

D. O(n^2) because each element can be visited multiple times during cycle checks

Solution

1. Step 1: Analyze outer and inner loops

   Each index is processed once in the outer loop; inner while loop visits elements until cycle or zero marking.

2. Step 2: Check effect of in-place marking

   Marking visited elements as zero prevents revisiting, ensuring total visits across all iterations is O(n).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   In-place marking guarantees linear time complexity [OK]

Hint: In-place marking -> each element visited once [OK]

Common Mistakes:

• Assuming repeated visits cause O(n²)
• Ignoring marking effect
• Confusing modulo cost as log factor

2. Examine the following buggy code for cycle detection using fast and slow pointers. Which line contains the subtle bug that can cause incorrect cycle detection or runtime error?

medium

A. Line 3: while fast and fast.next:

B. Line 5: slow = slow.next

C. Line 6: fast = fast.next.next

D. Line 4: if slow == fast:

Solution

1. Step 1: Understand pointer initialization and loop

   Both slow and fast start at head. The loop checks fast and fast.next to avoid null dereference.

2. Step 2: Identify when pointers are compared

   Comparing slow == fast before moving pointers causes immediate true at start (both at head), falsely detecting a cycle. Moving pointers first then comparing avoids this.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Comparison must happen after moving pointers to avoid false positive [OK]

Hint: Check pointers after moving, not before, to avoid false positives [OK]

Common Mistakes:

• Comparing pointers before moving them
• Not checking fast.next before advancing fast

3. Examine the following code snippet intended to detect the start of a cycle in a linked list. Identify the line containing the subtle bug that can cause a runtime error or infinite loop.

medium

A. Line 5: fast = fast.next.next

B. Line 3: while fast:

C. Line 7: if slow == fast:

D. Line 11: while ptr1 != ptr2:

Solution

1. Step 1: Check loop condition safety

   The loop condition only checks if fast is not None, but fast.next may be None, so fast.next.next can cause an exception.

2. Step 2: Identify fix

   The loop condition should check both fast and fast.next to avoid null pointer exceptions.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Accessing fast.next.next without checking fast.next causes runtime error [OK]

Hint: Always check fast and fast.next before accessing fast.next.next [OK]

Common Mistakes:

• Missing fast.next check
• Returning meeting point as cycle start
• Infinite loop due to wrong loop condition

4. Consider the following code snippet for palindrome check. Which line contains a subtle bug that can cause incorrect results on odd-length lists?

medium

A. Line where second_half_start is assigned by reversing slow

B. Line where slow pointer is advanced in the while loop

C. Line where first_half_start and second_half_start values are compared

D. Line where fast pointer is advanced in the while loop

Solution

1. Step 1: Understand midpoint selection

   For odd-length lists, slow points to the middle node, which should be skipped before reversal.

2. Step 2: Identify bug in reversal start

   Reversing from slow includes the middle node, causing mismatch in comparison.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Correct approach skips middle node before reversal on odd-length lists [OK]

Hint: Check if middle node is excluded before reversing second half [OK]

Common Mistakes:

• Reversing from slow without skipping middle node
• Incorrect fast/slow pointer advancement
• Not handling odd-length lists separately

5. If the linked list allows cycles (i.e., it may not terminate), which modification is necessary to safely find the nth node from the end?

hard

A. Use the two-pointer approach without changes; it will still work.

B. Use a stack to store nodes indefinitely until nth node is found.

C. First detect cycle using Floyd's cycle detection, then handle accordingly before finding nth node.

D. Increase n to a very large number to ensure traversal covers the cycle.

Solution

1. Step 1: Understand cycle impact

   If the list has a cycle, naive traversal will loop infinitely, breaking the algorithm.

2. Step 2: Detect and handle cycle

   Use Floyd's cycle detection to identify cycle presence and length, then adjust logic to avoid infinite loops.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Cycle detection is prerequisite for safe traversal [OK]

Hint: Detect cycle first to avoid infinite loops [OK]

Common Mistakes:

• Assuming list always terminates
• Using stack without cycle check
• Increasing n arbitrarily