Middle of the Linked List: Fast and slow pointers Pattern

Learning Outcome

After this lesson, you should be able to use fast and slow pointers to find the middle node in one pass.

Problem Statement

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

Brute Force Approach

Count the number of nodes, then walk again to index n / 2.

This is correct, but it needs two passes through the list.

Optimized Approach

Move slow one step and fast two steps. When fast reaches the end, slow has moved half as many steps, so it is at the middle.

Exact Pseudocode

slow = head
fast = head
while fast is not null and fast.next is not null:
  slow = slow.next
  fast = fast.next.next
return slow
  

Reference Code

class Solution:
    def middleNode(self, head):
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow
  

Sample Dry Run

Complexity

Edge Cases

• Single-node list returns the head.
• Even-length list returns the second middle.
• Empty list if platform allows it.

Interview Checklist

• Move fast two steps and slow one step.
• Use the loop condition fast != null and fast.next != null.
• Know whether the problem asks for first or second middle.

FAQs