Middle Node Value Retrieval — Problem Statement & Solution Guide

Linked ListEasyFast-Slow Pointers

TimeO(n)

SpaceO(1)

Problem Description

You are provided with the head of a singly linked list. Your task is to determine the integer value stored in the middle node of this list. The traversal must be completed in a single pass through the nodes, utilizing the fast-slow pointer technique to identify the target position without calculating the total length beforehand.

If the total number of nodes in the list is odd, the middle node is the one located at the exact center. If the total number of nodes is even, there are two central nodes; in this case, you must return the value of the second of these two nodes (the one closer to the tail).

The solution should not use recursion or additional data structures to store the nodes. The time complexity must be linear with respect to the number of nodes, and the space complexity must be constant.

DSA Pattern Breakdown

"Middle Node Value Retrieval"

easy

WHY DOES IT MATTER?

The fast‑slow pointer pattern provides a deterministic, constant‑space solution for problems that require knowledge of a list's midpoint, length parity, or cycle presence—all without a preliminary length calculation. This is crucial in memory‑constrained environments and when dealing with streams where a second pass is impossible.

OPTIMIZATION CHALLENGE

The key insight is to encode the list's total length implicitly through the relative speeds of two pointers, allowing the midpoint to emerge naturally when the faster pointer exhausts the list.

REAL-WORLD CONNECTION

Think of a conveyor belt (fast pointer) moving twice as fast as a quality‑control inspector (slow pointer). By the time the belt reaches the end of the factory floor, the inspector has examined exactly half the items, pinpointing the middle product without needing to count every item first.

During an interview, start by drawing the two‑pointer motion on paper; this visual cue often reveals off‑by‑one errors early and demonstrates to the interviewer that you understand the invariant that fast travels twice the distance of slow.

COMPLEXITY AT A GLANCE

⏱ Time:O(n)

💾 Space:O(1)

Core Theory — Why This Approach?

The fast‑slow pointer technique, often called the "tortoise and hare" algorithm, leverages two iterators moving at different speeds to infer positional relationships without a prior pass to compute length. By advancing the fast pointer two nodes for every single step of the slow pointer, when the fast pointer reaches the end of a singly linked list, the slow pointer will be exactly at the midpoint. This works because the distance covered by the fast pointer is twice that of the slow pointer, so the slow pointer has traversed half the total number of steps. The method is deterministic, requires only O(1) extra space, and guarantees a single traversal, making it ideal for large or streaming data where a second pass is prohibitive.

Naïve solutions typically involve first counting the nodes to obtain the length, then performing a second pass to the (length/2)th node. While conceptually simple, this double‑scan approach doubles the time spent on I/O-bound structures and can cause cache thrashing on massive lists. Moreover, in environments where the list is being generated on‑the‑fly (e.g., reading from a network socket), the total length may be unknown until the end, rendering the two‑pass method infeasible. The fast‑slow pattern eliminates these drawbacks by collapsing both phases into one, preserving linear time while keeping memory overhead constant.

From an algorithmic paradigm perspective, this problem exemplifies the broader class of "pointer‑chasing" techniques used in linked data structures. It demonstrates how relative motion can encode global properties (like length parity) locally, a principle that extends to cycle detection, palindrome verification, and even parallel processing pipelines where lagging stages infer the state of leading ones. Mastery of this pattern equips engineers to design efficient, single‑pass solutions across a spectrum of real‑world scenarios.

Interview Questions on This Problem

Q1How would you modify the fast‑slow pointer approach to return the second middle node in an even‑length list?

Initialize both pointers at the head, but move the fast pointer two steps while the slow pointer moves one step as usual; when the fast pointer reaches null (end), the slow pointer will be at the first middle. To get the second middle, simply advance the slow pointer one additional step before returning its value.

Q2Can the fast‑slow technique be used to detect a cycle in a singly linked list? Explain the adaptation.

Yes. By moving fast two steps and slow one step, if a cycle exists the two pointers will eventually meet inside the loop. If fast reaches null, the list is acyclic. This is known as Floyd's cycle‑finding algorithm.

Q3In a distributed system where nodes are streamed from multiple partitions, how would you compute the global middle element without storing all elements?

Apply a distributed version of the two‑pointer method: each partition maintains its own slow and fast counters, and a coordinator aggregates the fast counts to determine when the global fast pointer has traversed half the total elements, advancing the global slow pointer accordingly. This ensures O(1) per‑partition memory and a single pass over the streamed data.

Examples

Example 1

Input

head = [4, 2, 7, 1, 9]

Output

Explanation: The list contains 5 nodes (odd length). The middle index is 2 (0-based). The node at index 2 holds the value 7. Using fast-slow pointers: slow starts at index 0, fast at index 0. Step 1: slow->1, fast->2. Step 2: slow->2, fast->4. Fast reaches the end, so slow is at the middle node with value 7.

Example 2

Input

head = [3, 8, 5, 2]

Output

Explanation: The list contains 4 nodes (even length). The two middle nodes are at indices 1 and 2. We require the second middle node, which is at index 2. The node at index 2 holds the value 5. Using fast-slow pointers: slow starts at index 0, fast at index 0. Step 1: slow->1, fast->2. Step 2: slow->2, fast->3 (end). Slow stops at index 2, which is the second middle node.

Example 3

Input

head = [10]

Output

Explanation: The list contains 1 node. The only node is the middle node. Its value is 10. Fast and slow both start at the head. Since fast is at the end immediately, the loop terminates, and slow remains at the head.

Example 4

Input

head = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Output

Explanation: The list contains 10 nodes (even length). The middle nodes are at indices 4 and 5. We need the second one, at index 5. The value at index 5 is 6. Fast moves 2 steps per iteration, slow 1 step. After 5 iterations, fast is at index 9 (end), and slow is at index 5.

Constraints

1 <= number of nodes <= 10^5
-10^9 <= node.val <= 10^9
The linked list is guaranteed to be non-circular and valid.
You must solve this in O(n) time and O(1) space.

Optimal Approach & Strategy

Use two pointers moving at different speeds (slow by 1, fast by 2) in a single traversal; when fast reaches the end, slow points to the middle node.

Brute Force Approach

First traverse the list to count nodes, then compute length/2 and traverse again to that index to fetch the middle value.

Verified Code Solutions

Language:

JavaScript Solution

Time: O(n)

function middleNode(head) {
   let slow = head;
   let fast = head;
   while (fast && fast.next) {
       slow = slow.next;
       fast = fast.next.next;
   }
   return slow.val;
}

class Solution {
public:
   int middleNode(ListNode* head) {
       ListNode* slow = head;
       ListNode* fast = head;
       while (fast && fast->next) {
           slow = slow->next;
           fast = fast->next->next;
       }
       return slow->val;
   }
};

class Solution {
   public int middleNode(ListNode head) {
       ListNode slow = head;
       ListNode fast = head;
       while (fast != null && fast.next != null) {
           slow = slow.next;
           fast = fast.next.next;
       }
       return slow.val;
   }
}

def middleNode(head):
   slow = head
   fast = head
   while fast and fast.next:
       slow = slow.next
       fast = fast.next.next
   return slow.val

function middleNode(head) {
   let slow = head;
   let fast = head;
   while (fast && fast.next) {
       slow = slow.next;
       fast = fast.next.next;
   }
   return slow.val;
}

Solve in Interative Editor

Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.

Middle Node Value Retrieval Solution

Problem Statement

Input

Output

Input

Output

Input

Output

Input

Output

Constraints

More Linked List

Optimized Approach

Brute Force Approach

Step-by-Step Dry Run

Tested Solutions

Middle Node Value Retrieval — Problem Statement & Solution Guide

Problem Description

DSA Pattern Breakdown

Core Theory — Why This Approach?

Interview Questions on This Problem

Examples

Constraints

Optimal Approach & Strategy

Brute Force Approach

Verified Code Solutions

Solve in Interative Editor