[/dsa/leetcode]

876 - Middle of the Linked List

Friday, 18 September 2026

<easy> [problem]

One pointer moving twice as fast as the other arrives at the end exactly when the slow one reaches the middle, so the length never has to be measured.

{linked list}{two pointers}

Problem

Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one.

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

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

Constraints:

  • The number of nodes is in the range [1, 100]
  • 1 <= Node.val <= 100

The output is shown as a list because the node is returned, and printing from it prints the rest of the list.

Approach

The obvious version is two passes: count the nodes, then walk n / 2 of them. That’s O(n) and perfectly fine. The one-pass version replaces the counting with a rate difference.

Move fast two nodes for every one that slow moves. Distance travelled stays in a fixed ratio, so when fast has covered the whole list, slow has covered exactly half of it:

1 -> 2 -> 3 -> 4 -> 5
s
f

1 -> 2 -> 3 -> 4 -> 5
     s
          f

1 -> 2 -> 3 -> 4 -> 5
          s
                    f     fast->next is null, stop -> slow is the middle
  • fast->next — stops when fast is on the last node, which is the odd-length case.
  • fast — stops when fast has run off the end entirely, which is the even-length case, and also prevents dereferencing null on the next fast->next.
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head, *fast = head;
        while(fast && fast->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        return slow;
    }
};
  • time: O(n) - fast traverses the list once
  • space: O(1) - two pointers
quantinium © 2026