Middle of the Linked List

Problem Summary

(Write in your own words, not copied from LeetCode. This forces comprehension.)

• Given a linked list, find the middle point

Key Observations

(Patterns, constraints, or hints in the problem statement.)

• Find the middle in $O(1)$ space

Main Concepts Used

(Mark the CS concepts or algorithms used.)

• Fast & Slow Pointers

Time & Space Complexity

• Time: $O(n)$ → Reason: Iterating through the linked list once
• Space: $O(1)$ → Reason: Not storing a copy

Code

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