## Problem Statement#

### Description#

Given the `head` of a singly linked list, return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

### Examples#

#### Example 1:#

flowchart LR a((1))-->b((2))-->c(3)-->d((4))-->e((5))
``````Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
``````

#### Example 2:#

flowchart LR a((1))-->b((2))-->c((3))-->d(4)-->e((5))-->f((6))
``````Input: head = [1,2,3,4,5,6]
Output: [4,5,6]
Explanation: Since the list has two middle nodes
with values 3 and 4, we return the second one.
``````

### Constraints#

• The number of nodes in the list is in the range `[1, 100]`.
• `1 <= Node.val <= 100`

## Key Insights#

The most straight forward way to approach this problem is to find the number of nodes in the list and then return node `n // 2` (zero-indexed). If we have `6` nodes in the linked list, we will get node `3`. If we have `5` nodes, we will get node `2`.

We are essentially returning the second half of the linked list. If the length of the list is even, we have two equal halves. If the length is odd, the second half is one node longer than the first half.

flowchart LR a((0))-->b((1))-->c((2))-->d(3)-->e((4))-->f((5))
flowchart LR a((0))-->b((1))-->c(2)-->d((3))-->e((4))

In the previous approach we found the middle node in two passes. Although this is linear time `O(N)`, there is a better way. We can actually achieve one-pass linear time if we use two pointers. If the `fast` pointer advances two nodes for every one node the `slow` pointer moves, by the time `fast` or `fast.next` reaches the end, the `slow` pointer will point to the middle node.

## Python Solution#

### Two Passes#

``````# 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: Optional[ListNode]) -> Optional[ListNode]:
n = 0

# find the length of the linked list
while curr:
n += 1
curr = curr.next

# Traverse up to the middle node
for i in range(n//2):
curr = curr.next

# Return the middle node
return curr
``````

### Two Pointers#

``````class Solution:
def middle(self, head: "ListNode") -> "ListNode":
"""
T: O(N)
S: O(1)
"""
# Initialize two pointers
"""
Case 1: (even length)
1-->2-->3-->4
^slow
^fast

Case 2: (odd length)
1-->2-->3-->4-->5
^slow
^fast
"""

# Every time the slow pointer advances one,
# the fast pointer advances two. If the list
# has an even number of nodes, the fast pointer
# will overshoot the end and the slow pointer
# will be the head of the second half of the list.
# If the list has an odd number of nodes, the fast
# pointer will end on the last node, and the slow
# pointer will land on the middle node
while fast and fast.next:
slow = slow.next
fast = fast.next.next

return slow
``````