Coding interview problems › Linked Lists

🔗 Linked Lists Easy

Middle of the Linked List

Find the middle node of a linked list in one pass: the fast pointer moves two steps for each step of the slow one. Tested Python, live visual.

Also searched as: find middle of linked list · slow and fast pointer middle node · middle element of linked list in one pass

🔗

Try it live Free

Linked Lists: Reverse & Floyd's Cycle

The tortoise and hare in the linked list lab are the same two pointers; here, instead of waiting for them to meet in a cycle, you stop when the hare reaches the end.

Open the playground →

The problem

Given the head of a non-empty singly linked list, return its middle node. If the list has an even number of nodes, return the second of the two middle nodes.

Input1 -> 2 -> 3 -> 4 -> 5
Outputnode 3
Input1 -> 2 -> 3 -> 4
Outputnode 3

Two middles, 2 and 3; return the second.

The key insight

If one pointer moves twice as fast as another, then when the fast one reaches the end, the slow one is exactly halfway. This finds the middle in a single pass without knowing the length in advance.

Brute force first: Count the nodes in one pass, then walk n // 2 steps in a second pass. It is also O(n), but takes two passes.

Step-by-step approach

  1. Start slow and fast at head.
  2. While fast and fast.next exist, move slow one step and fast two steps.
  3. Return slow.

Python solution

PYTHON 3tested
class ListNode:
    def __init__(self, val=0, next=None):
        self.val, self.next = val, next


def middle_node(head):
    slow = fast = head
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
    return slow          # second middle when the length is even

Complexity

TimeO(n)
SpaceO(1)

The fast pointer covers the list in about n/2 iterations, and only two pointers are kept.

Common mistakes

Frequently asked questions

What is the time and space complexity?

O(n) time in a single pass and O(1) extra space.

How do I get the first middle node for an even-length list?

Loop while fast.next and fast.next.next exist. That stops one step earlier, leaving slow on the first of the two middles, which is what you want when splitting a list in half for merge sort or Reorder List.

Why not just count the length first?

Counting first and walking again is correct and still O(n). The two-pointer version does it in one pass and is the pattern behind cycle detection and other problems.

Where is this used?

Merge sort on linked lists, Palindrome Linked List and Reorder List all start by finding the middle with slow and fast pointers.

Preparing for placements?

Take the 2-minute readiness check to find your weak patterns, then follow the placement path from DSA core to system design.

📋 2-minute readiness check The full placement path

All coding interview problems More Linked Lists Linked Lists: Reverse & Floyd's Cycle lab Placement prep guides

Problem statements on this site are written in our own words. Problem names are the common names used across interview-prep communities; BitBootcamp is an independent learning platform and is not affiliated with LeetCode or any company that asks these questions.