Find the middle of a linked list in one pass

You're in a phone screen at Amazon and the interviewer asks, "Given a linked list, can you find the middle node in a single pass?" It sounds straightforward, but there's a catch: you can't simply count all the nodes and then walk to the midpoint, because that would require two passes. This problem, also known as Middle of the Linked List, tests whether you know the slow and fast pointer technique, one of the most elegant tricks in the linked list toolbox. Get this one down and you'll have the foundation for cycle detection, palindrome checking, and merge sort on linked lists.

TL;DR

Use two pointers, slow and fast, both starting at the head. Move slow one step and fast two steps in each iteration. When fast reaches the end (null or its next is null), slow is sitting at the middle node. Return slow.data. This runs in O(n) time and O(1) space. For even-length lists, it returns the second of the two middle nodes.

Why This Problem Matters

Finding the middle of a linked list in one pass is a gateway problem. It introduces the slow/fast pointer pattern (sometimes called the tortoise and hare), which is a recurring technique in linked list questions. Once you understand why moving at two different speeds locates the midpoint, you can apply the same idea to detect cycles, find the start of a cycle, or split a list for merge sort. It is a favorite warm-up at companies like Amazon precisely because it bridges basic linked list traversal and more advanced pointer manipulation.

Linked Lists: A Quick Refresher

A singly linked list is a chain of nodes where each node holds a value and a reference to the next node. Unlike arrays, you can't jump to the middle by index. You have to walk from the head, one node at a time.

Key characteristics:

• Nodes: Each contains data and a next pointer
• Head: The entry point to the list
• Tail: The last node, pointing to null
• Sequential access only: No random indexing

Understanding the Problem

Given: The head of a singly linked list Task: Find and return the data of the middle node in one pass Constraint: Constant space, one traversal

findMiddle([1]) -> 1
findMiddle([1->2]) -> 2
findMiddle([1->2->3->4]) -> 3
findMiddle([1->2->3->4->5]) -> 3

For even-length lists, the second of the two middle nodes is returned. In [1, 2, 3, 4], nodes 2 and 3 are both "middle," and the method returns 3.

Edge Cases

1. Single node: The head is the middle. Return its data.
2. Two nodes: Return the second node's data.
3. Odd length: Exactly one middle node.
4. Even length: Two candidates; return the second one.

Solution Approach

The naive approach would traverse the list once to count nodes, then traverse again to the midpoint. That works, but it takes two passes. Can we do it in one?

Here is the key insight: if one pointer moves twice as fast as another, by the time the fast pointer reaches the end, the slow pointer will have covered exactly half the distance. Think of two runners on a track. If one runs at double the speed, when the fast runner finishes a lap, the slow runner is at the halfway mark.

This gives us the algorithm:

1. Start both slow and fast at the head
2. Move slow forward by one node per step
3. Move fast forward by two nodes per step
4. When fast can't move further, slow is at the middle

Tracing Through [1, 2, 3, 4, 5]

Let's watch the pointers move:

After two iterations, fast is at node 5 and fast.next is null. The loop exits, and slow is at node 3, which is the middle. We return 3.

Tracing Through [1, 2, 3, 4] (Even Length)

After step 2, fast has moved past the end (it's null). The loop exits, and slow is at node 3. For even-length lists, the second middle node is returned.

Single Element [1]

The loop condition fails immediately because fast.next is null. We return slow.data, which is 1.

Implementation

Prefer a different language? Jump to solutions in other languages.

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

Let's break this down:

1. Initialize both pointers at head: slow and fast start at the same position
2. Loop while fast can advance two steps: We check both fast != null (even-length termination) and fast.next != null (odd-length termination)
3. Advance slow by 1, fast by 2: This is the core of the technique
4. Return slow.data: When the loop exits, slow is at the middle

The condition order matters. Checking fast != null first short-circuits evaluation so we never call .next on a null reference.

Complexity Analysis

Time Complexity: O(n)

The fast pointer traverses the entire list (n nodes), and the slow pointer traverses half (n/2 nodes). Each step is O(1) work. Total: O(n).

Space Complexity: O(1)

Only two pointer variables are used regardless of list size. No arrays, no stacks, no extra data structures.

Why Not Two Passes?

The two-pass approach (count nodes, then walk to the middle) is also O(n) time and O(1) space. Both are technically correct. But interviewers specifically ask for "one pass" to test whether you know the slow/fast pointer technique. This pattern is a prerequisite for harder problems like cycle detection, so demonstrating it here shows stronger fundamentals.

Common Pitfalls

1. Wrong loop condition: Using only fast.next != null crashes on even-length lists because fast becomes null before you check .next.

   // Wrong - crashes on [1, 2]
   while (fast.next != null) { ... }
   // Correct - handles both even and odd lengths
   while (fast != null && fast.next != null) { ... }
   

2. Starting fast at head.next: Some variants start fast one step ahead, which shifts which middle node is returned for even-length lists. Make sure your starting positions match the expected behavior.

3. Returning the node instead of the data: The problem asks for the data value, not the node itself. Return slow.data, not slow.

Interview Tips

When presenting this solution:

1. Name the technique: Say "I'll use the slow and fast pointer technique" or "tortoise and hare." Interviewers like hearing pattern names.

2. Draw the list: Sketch [1, 2, 3, 4, 5] and show slow/fast positions at each step. Visual traces catch logic errors before you write code.

3. Explain the loop condition: Walk through why you need both checks. This shows you've thought about edge cases.

4. Mention follow-ups: "This same technique can detect cycles in a linked list" or "I could use this to split a list for merge sort." Showing connections to harder problems demonstrates depth.

5. Discuss even vs odd: Mention that even-length lists have two middle candidates and explain which one your code returns.

Key Takeaways

• The slow/fast pointer technique finds the middle of a linked list in one pass with O(n) time and O(1) space, using two pointers that move at different speeds.
• The loop condition fast != null && fast.next != null handles both even and odd list lengths without null pointer exceptions.
• For even-length lists, this approach returns the second of the two middle nodes.
• This pattern is foundational for harder linked list problems including cycle detection (Floyd's algorithm), merge sort on linked lists, and palindrome checking.
• Always trace through at least three cases (single node, odd length, even length) to verify your pointer logic before coding.

Practice and Related Problems

Once you've nailed the slow/fast pointer for finding the middle, try these progressions:

• Detect a cycle in a linked list (Floyd's cycle detection)
• Find the start of a cycle in a linked list
• Check if a linked list is a palindrome (split at middle, reverse second half)
• Merge sort a linked list (split at middle recursively)

This problem and hundreds of others are available on Firecode, where consistent daily practice helps you build the pattern recognition that top tech companies look for. Whether you're warming up for phone screens or preparing for on-site interviews, mastering fundamentals like the slow/fast pointer sets you up well.

Solutions in Other Languages

Python

class Solution:
    def find_middle(self, head: ListNode) -> int:
        slow = fast = head
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next

        return slow.data

JavaScript

class Solution {
  findMiddle(head) {
    let slow = head, fast = head;
    while (fast !== null && fast.next !== null) {
      slow = slow.next;
      fast = fast.next.next;
    }
    return slow.data;
  }
}

TypeScript

class Solution {
  findMiddle(head: ListNode): number {
    let slow: ListNode | null = head, fast: ListNode | null = head;
    while (fast !== null && fast.next !== null) {
      slow = slow!.next;
      fast = fast.next.next;
    }
    return slow!.data;
  }
}

C++

class Solution {
public:
  int findMiddle(ListNode *head) {
    ListNode *slow = head, *fast = head;
    while (fast != nullptr && fast->next != nullptr) {
      slow = slow->next;
      fast = fast->next->next;
    }
    return slow->data;
  }
};

Go

package solution

import . "firecode.io/custom_types"

func (s *Solution) FindMiddle(head *ListNode) int {
	slow, fast := head, head
	for fast != nil && fast.Next != nil {
		slow = slow.Next
		fast = fast.Next.Next
	}
	return slow.Data
}

Scala

class Solution {
  def findMiddle(head: ListNode): Int = {
    var slow = head
    var fast = head
    while (fast != null && fast.next != null) {
      slow = slow.next
      fast = fast.next.next
    }
    slow.data
  }
}

Kotlin

class Solution {
    fun findMiddle(head: ListNode?): Int {
        var slow = head
        var fast = head
        while (fast != null && fast.next != null) {
            slow = slow?.next
            fast = fast.next?.next
        }
        return slow?.data ?: 0
    }
}

Swift

import Foundation

class Solution {
    func findMiddle(_ head: ListNode?) -> Int {
        var slow = head
        var fast = head
        while fast != nil && fast?.next != nil {
            slow = slow?.next
            fast = fast?.next?.next
        }
        return slow?.data ?? 0
    }
}

Rust

pub struct Solution;

impl Solution {
    pub fn find_middle(&self, head: Option<Box<ListNode>>) -> i32 {
        let mut slow = &head;
        let mut fast = &head;
        while fast.is_some() && fast.as_ref().unwrap().next.is_some() {
            slow = &slow.as_ref().unwrap().next;
            fast = &fast.as_ref().unwrap().next.as_ref().unwrap().next;
        }
        slow.as_ref().unwrap().data
    }
}

C#

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

Dart

class Solution {
  int findMiddle(ListNode? head) {
    ListNode? slow = head;
    ListNode? fast = head;
    while (fast != null && fast.next != null) {
      slow = slow?.next;
      fast = fast.next?.next;
    }
    return slow?.data ?? 0;
  }
}

PHP

class Solution {
    public function findMiddle(ListNode $head): int {
        $slow = $head;
        $fast = $head;
        while ($fast !== null && $fast->next !== null) {
            $slow = $slow->next;
            $fast = $fast->next->next;
        }
        return $slow->data;
    }
}

Ruby

class Solution
  def find_middle(head)
    slow, fast = head, head
    while fast && fast.next
      slow = slow.next
      fast = fast.next.next
    end
    slow.data
  end
end