Skip to main content
DSA patterns

Middle of the Linked List

easyLinked list Must-doWiproTCSCognizant

Problem statement

You're given the head of a singly linked list. Return the middle node of the list.

If the list has an odd number of nodes, there's one obvious middle. If it has an even number of nodes, there are two middle nodes — in that case, return the second of the two.

Examples

Example 1

Input: head = [1,2,3,4,5]

Output: [3,4,5]

Explanation: The list has 5 nodes, so there's one clear middle: node 3, and everything from there to the end is shown as the output.

Example 1

Example 2

Input: head = [1,2,3,4,5,6]

Output: [4,5,6]

Explanation: The list has 6 nodes, so there are two middle nodes (3 and 4) — the problem asks for the second one, node 4, and everything from there onward.

Example 2

Hints

Hint 1: If you already knew exactly how many nodes were in the list, you could work out which position the middle node sits at — but reaching it would still take a second walk from the head, since a linked list has no way to jump straight to an index.

Approach

Optimal: Fast and slow pointers

Intuition

Instead of counting the nodes first and then walking to the middle, use two pointers that both start at the head but move at different speeds: a slow pointer that moves one node at a time, and a fast pointer that moves two nodes at a time. By the time fast has covered the whole list (twice as fast as slow), slow has covered exactly half of it — landing precisely on the middle node, without ever needing to count anything first.

Steps

  1. Set both slow and fast to head.
  2. While fast is not null and fast.next is not null:
    • Move slow forward by one node.
    • Move fast forward by two nodes.
  3. Once the loop stops (because fast fell off the end), slow is sitting on the middle node — return it.

Dry run

head = [1, 2, 3, 4, 5, 6]

step slow fast
start 1 1
1 2 3
2 3 5
3 4 (fast->next was null, so fast becomes null)

The loop stops once fast becomes null, and slow is left pointing at the node with value 4 — the second of the two middle nodes, matching the expected output.

Edge cases: a list with a single node never enters the loop at all (fast.next is already null), so slow stays at head and is correctly returned as the only, and therefore middle, node. A list with two nodes runs the loop exactly once, leaving slow on the second node — matching the rule of returning the second middle when there's a tie.

Complexity

Time O(n) - fast visits every node (moving two at a time) exactly once over the course of the list, and slow moves in lockstep at half that speed, so the whole list is still only walked once, not twice.

Space O(1) - only the two pointers, slow and fast, are kept, no matter how long the list is.

# Definition for singly-linked list.
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next


class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow


def build_list(values):
    head = ListNode(values[0])
    current = head
    for v in values[1:]:
        current.next = ListNode(v)
        current = current.next
    return head


def to_list(node):
    values = []
    while node:
        values.append(node.val)
        node = node.next
    return values


if __name__ == "__main__":
    print(to_list(Solution().middleNode(build_list([1, 2, 3, 4, 5]))))       # [3, 4, 5]
    print(to_list(Solution().middleNode(build_list([1, 2, 3, 4, 5, 6]))))    # [4, 5, 6]
RecapThe whole problem in a few lines, for the night before
  • Spot it: "find the middle node" of a singly linked list, where you can't jump to an index directly
  • Idea: fast/slow pointers — fast moves two nodes at a time, slow moves one; when fast runs out of room, slow is at the middle
  • Cost: O(n) time, O(1) space (counting first then walking again is also O(n) time, but needs two full passes)
  • Trap: getting the loop condition wrong (checking only fast != null instead of also fast.next != null) causes a null-pointer error when fast tries to take its second step

Interview follow-ups

  • What if you needed the first middle node instead of the second, when there's a tie?

    Change the loop condition so fast stops one step earlier: loop while fast.next is not null and fast.next.next is not null. That makes fast advance one fewer double-step overall, which leaves slow on the earlier of the two middle nodes instead.

  • What if the list could be circular (the last node points back into the list instead of ending in null)?

    The same fast/slow pointers, moving at speeds of one and two nodes per step, are also exactly how Floyd's cycle detection works: if the list is circular, fast will eventually lap slow and the two pointers will meet at the same node, which is impossible in a normal, null-terminated list. Checking for that meeting point is how you'd detect the cycle before trying to find any kind of "middle" at all.

Frequently asked questions

Whatever distance fast has covered when it reaches the end of the list, slow has covered exactly half of that distance, because it always moves at half the speed. Since fast covers the full length of the list, slow ends up exactly halfway through it — which is the definition of the middle.

With an even number of nodes, fast runs out of room to take its next full two-step move exactly when slow has taken half as many single steps, and that half-count lands slow on the later of the two middle nodes rather than the earlier one. Working through the dry run for a 6-node list shows this directly: slow ends on the node with value 4, not 3.

The fast/slow (or "tortoise and hare") two-pointer technique is the same idea used to detect a cycle in a linked structure, find where two references have converged, or split a sequence in half without knowing its length up front — situations that come up when reasoning about linked data structures like intrusive lists in low-level systems code.

Not really for this problem — fast/slow does the same job in a single pass and constant extra space, so it's strictly better here. The two-pass approach is worth knowing mainly because it's the natural first idea, and because the counting step it relies on is reused in other linked-list problems, like finding the nth node from the end.