💬 Discord
Sign In
NeetCode #309LC-876EasyLinked List
← Back to All Problems

#309 · #876 · Middle of the Linked List(链表的中间结点)

📌 Problem Statement & Constraints

Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second one. Constraints: the number of nodes is in [1, 100].

💡 Core Algorithmic Approaches

  1. Move a slow pointer one step and a fast pointer two steps per iteration.
  2. When the fast pointer reaches the end, the slow pointer is at the middle.
  3. Because the fast pointer advances two at a time, it lands on None for even lengths, which leaves slow on the second middle node -- exactly as required.
  4. This is the first half of the Reorder List and Palindrome Linked List solutions.

💻 Benchmark Python3 Implementation

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

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): one pass at double speed.
💾 Space Complexity
O(1): two pointers.

⚠️ Interview Pitfalls & Follow-ups

  • Using while fast alone: fast.next.next would raise an AttributeError.
  • Returning the first middle node: for even lengths the requirement is the second one, which this formulation gives.
  • Counting the length first: two passes instead of one.
  • Advancing the pointers in the wrong order: slow must be advanced before fast, but since they are independent, either order works as long as both advance by their own step count.