104 Middle of the Linked List

 Given: A singly linked list.

Goal: Return the middle node of the linked list.
If there are two middle nodes, return the second one.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: 3

Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: 4


Approach: Two-Pointer (Fast and Slow Pointer)
Idea:
Use two pointers:
Slow pointer: moves one step at a time.
Fast pointer: moves two steps at a time.

How It Works:
When the fast pointer reaches the end of the list, the slow pointer will be at the middle.

Why It Works:
Fast pointer covers double the distance of slow pointer.

So when fast is at the end (or past the end), slow has reached halfway.

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head: ListNode) -> ListNode:
    slow = head
    fast = head

    while fast and fast.next:
        slow = slow.next        # move 1 step
        fast = fast.next.next   # move 2 steps

    return slow