Problems/Fast and Slow Pointers/Linked List Midpoint
Fast and Slow Pointers
easy

Linked List Midpoint

The problem is to efficiently find the middle node of a singly linked list. This is a classic interview question that tests your understanding of linked list manipulation and algorithm optimization.

linked-listfast-and-slow-pointerstwo-pointersalgorithm

Problem Statement

Given the head of a singly linked list, your task is to locate and return the node that resides in the middle of the list. If the linked list has an even number of nodes, return the first of the two middle nodes.

Example 1
Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 3
The linked list has 5 nodes. The middle node is 3.
Example 2
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 3
The linked list has 6 nodes. The two middle nodes are 3 and 4. We return the first one, which is 3.
Constraints
  • -The linked list will contain at least one node.
  • -All node values are unique.
  • -The linked list is singly linked.

Brute Force Approach

The most straightforward approach is like measuring a rope to find its midpoint. First, traverse the entire linked list to determine its length. Then, traverse it again, stopping at the node that represents the midpoint based on the calculated length.

TimeO(n)
SpaceO(1)

Ready to practice?

Work through this problem with AI coaching and get real-time feedback

Practice This Problem