## 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:

```
Input: head = [1,2,3,4,5]
Output: [3,4,5]
Explanation: The middle node of the list is node 3.
```

#### Example 2:

```
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.

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
curr = head
# find the length of the linked list
while curr:
n += 1
curr = curr.next
curr = head
# 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
slow = head
fast = head
"""
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
```