Middle of the Linked List

Given head, the first node of a non-empty singly linked list, return the node that sits in the middle of the list.

If the list has an odd number of nodes there is a single middle node. If it has an even number, there are two central nodes; return the second of them (the one closer to the tail).

Lists are written as arrays from head to tail. Because you return a node, the judge shows your answer as that node followed by everything after it, so returning the node with value 9 in [3,6,9,12,15] is displayed as [9,12,15].

Example 1

Example 2

Example 3

Constraints

• The number of nodes is between 1 and 104.
• 1 <= Node.val <= 100

Pattern Path · Linked Lists · problem 69 of 169

Start simple

Count the nodes in one pass, then walk n // 2 steps from the head: O(n) time, O(1) space, but two passes (copying into an array instead costs O(n) space).

The key idea

Use the fast and slow pointer technique. Both start at head. In each round, slow advances one node and fast advances two. Keep going while fast and fast.next both exist.

Why it lands on the middle: after k rounds, slow is at index k and fast at index 2k. The loop stops once fast can no longer take two steps, i.e. when 2k reaches the last index (odd length) or one past it (even length). In both cases k = ⌊n / 2⌋, which is exactly the middle node for odd n and the second of the two middle nodes for even n.

The loop condition decides which middle you get. Checking fast.next and fast.next.next instead would stop one step earlier and return the first middle, a variant needed when splitting a list for merge sort.

Complexity

• Time: O(n)
• Space: O(1)

Python

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = fast = head
        while fast and fast.next:
            slow = slow.next         # one step
            fast = fast.next.next    # two steps
        return slow

JavaScript

var middleNode = function(head) {
  let slow = head;
  let fast = head;
  while (fast && fast.next) {
    slow = slow.next;       // one step
    fast = fast.next.next;  // two steps
  }
  return slow;
};

What the interviewer is checking

It introduces the fast/slow pointer pattern and checks that you can reason precisely about loop conditions and which middle node they produce.

Mistakes to avoid

• Returning the first middle node on even-length lists because of the wrong loop condition.
• Accessing fast.next.next without first checking that fast.next exists.
• Returning the value instead of the node.

Follow-ups to expect

• Return the first middle instead. (Stop when fast.next.next is null.)
• Detect whether the list has a cycle. (Fast and slow pointers meet.)
• Is the list a palindrome in O(1) space? (Find middle, reverse second half.)

In real software

Splitting a linked list in half is the first step of merge sort on linked structures, and the two-speed pointer trick also powers cycle detection in iterators and memory graphs.

Practice next