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. Consider the following Python function that deletes N nodes after skipping M nodes in a linked list. Given the linked list 1 -> 2 -> 3 -> 4 and parameters M=1, N=1, what is the linked list after calling delete_n_after_m_optimized(head, 1, 1)?

easy

A. 1 -> 3 -> 4

B. 2 -> 3 -> 4

C. 1 -> 2 -> 4

D. 1 -> 4

Solution

1. Step 1: Trace skipping M=1 node

   Starting at node 1, skip 1 node means stay at node 1 (loop runs zero times).

2. Step 2: Delete N=1 node after current

   Delete node after 1, which is node 2. So, link node 1's next to node 3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Resulting list is 1 -> 3 -> 4 after deletion [OK]

Hint: Skipping M=1 means no move; delete next N=1 node [OK]

Common Mistakes:

• Off-by-one in skipping nodes
• Deleting wrong nodes after skipping
• Misunderstanding loop ranges

2. You are given a problem where you repeatedly transform a number by replacing it with the sum of the squares of its digits. The goal is to determine if this process eventually reaches 1 or falls into a repeating cycle. Which algorithmic approach is best suited to efficiently detect cycles in this implicit sequence without extra space?

easy

A. Dynamic Programming with memoization to store intermediate results

B. Breadth-First Search (BFS) to explore all possible transformations

C. Greedy approach to pick the next number with the smallest digit sum

D. Floyd's Cycle Detection (Fast and Slow Pointers) to detect cycles in sequences

Solution

1. Step 1: Understand the problem as detecting cycles in a sequence generated by a function

   The problem involves repeatedly applying a function to a number to generate a sequence. Detecting if this sequence reaches 1 or cycles indefinitely is a classic cycle detection problem.

2. Step 2: Identify Floyd's Cycle Detection as the optimal approach

   Floyd's fast and slow pointers efficiently detect cycles in sequences without extra space, unlike DP or BFS which require additional memory or are not suited for implicit sequences.

3. Final Answer:

   Option D -> Option D

4. Quick Check:

   Cycle detection in implicit sequences -> Floyd's algorithm [OK]

Hint: Cycle detection in sequences -> Floyd's fast-slow pointers [OK]

Common Mistakes:

• Confusing cycle detection with DP or BFS approaches

3. Given the following Python code for reorderList and the input list 1->2->3->4, what is the value of the node pointed to by left after the first merge step in the recursion unwinding?

easy

A. Node with value 3

B. Node with value 2

C. Node with value 4

D. Node with value 1

Solution

1. Step 1: Trace recursion to the end

   Recursion reaches right = None, then unwinds from node 4 back to node 1.

2. Step 2: First merge step during unwinding

   At right=4, left=1, tmp=left.next=2; left.next=4; 4.next=2; left=2 after merge.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   After first merge, left points to node with value 2 [OK]

Hint: left moves forward after merging right node [OK]

Common Mistakes:

• Confusing left pointer update
• Off-by-one in recursion unwind
• Misreading next pointer assignments

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

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