Domain 1EasyCORE

Middle of the Linked List

The problem requires finding the middle node of a singly linked list. The input is a non-empty singly linked list with a head node `head`. The output should be the middle node of the list. If there are two middle nodes (i.e., the list has an even number of nodes), we return the second middle node.

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Linked List

876. Middle of the Linked List

Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 0
Acceptance rate: 69.2%


Problem Breakdown

The problem requires finding the middle node of a singly linked list. The input is a non-empty singly linked list with a head node head. The output should be the middle node of the list. If there are two middle nodes (i.e., the list has an even number of nodes), we return the second middle node.

Inputs:

  • A non-empty singly linked list with a head node head.

Outputs:

  • A ListNode object representing the middle node of the list.

Implicit Constraints or Tricky Edge Cases:

  • The list can have between 1 and 100 nodes.
  • If the list has an even number of nodes, return the second middle node.

Intuition

A brute-force approach would involve traversing the linked list to count the total number of nodes and then traversing again to find the middle node. This approach is inefficient because it requires two passes through the list, resulting in a time complexity of O(n).

The key insight for a better approach is to use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Approach

  1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
  2. Traverse the list with the fast pointer moving two steps at a time and the slow pointer moving one step at a time.
  3. When the fast pointer reaches the end of the list (i.e., fast is None or fast.next is None), the slow pointer will be at the middle node.
  4. Return the slow pointer as the result.

This approach ensures that we only traverse the list once, achieving a time complexity of O(n) with a space complexity of O(1).

Complexity Analysis

  • Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once.
  • Space Complexity: O(1). We use only two pointers regardless of the size of the input.

Solution

# 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

Edge Cases Handled

  • Single Node List: If the list contains only one node, both slow and fast will point to that node, and it will be returned correctly.
  • Even Number of Nodes: The algorithm naturally returns the second middle node when the list has an even number of nodes by moving the slow pointer one step further in each iteration.