# LeetCode 876: Middle of the Linked List

## Problem Restatement

We are given the `head` of a singly linked list.

We need to return the middle node of the linked list.

If the linked list has two middle nodes, we return the second middle node. For example, in a list with 6 nodes, nodes 3 and 4 are both middle candidates, so we return node 4. LeetCode states this rule explicitly.

## Input and Output

| Item | Meaning |
|---|---|
| Input | `head`, the first node of a singly linked list |
| Output | The middle node of the linked list |
| Even length rule | Return the second middle node |
| Return type | `ListNode` |

Example function shape:

```python
def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    ...
```

## Examples

Example 1:

```text
Input:  head = [1,2,3,4,5]
Output: [3,4,5]
```

The list has 5 nodes.

The middle node is the 3rd node, whose value is `3`.

Returning the node with value `3` means the visible output is:

```text
[3,4,5]
```

because LeetCode displays the returned node and every node after it.

Example 2:

```text
Input:  head = [1,2,3,4,5,6]
Output: [4,5,6]
```

The list has 6 nodes.

There are two middle nodes: value `3` and value `4`.

The problem asks for the second middle node, so we return the node with value `4`.

## First Thought: Store Nodes in an Array

A simple way is to walk through the linked list and store every node in an array.

Then we return the node at index:

```python
len(nodes) // 2
```

For odd length:

```text
[1,2,3,4,5]
```

There are 5 nodes.

```python
5 // 2 == 2
```

Index `2` is the node with value `3`.

For even length:

```text
[1,2,3,4,5,6]
```

There are 6 nodes.

```python
6 // 2 == 3
```

Index `3` is the node with value `4`, which is the second middle node.

Code:

```python
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        nodes = []

        curr = head
        while curr:
            nodes.append(curr)
            curr = curr.next

        return nodes[len(nodes) // 2]
```

This works, but it stores all nodes, so it uses extra memory.

## Problem With the Array Approach

The array approach uses `O(n)` extra space.

We can do better because we only need one node: the middle node.

A linked list can be scanned with pointers. We do not need random access if we can arrange for one pointer to reach the middle exactly when another pointer reaches the end.

## Key Insight

Use two pointers:

| Pointer | Movement |
|---|---|
| `slow` | Moves 1 node at a time |
| `fast` | Moves 2 nodes at a time |

Both pointers start at `head`.

When `fast` reaches the end of the list, `slow` has moved about half as many steps.

That means `slow` is at the middle.

This also handles the even length rule correctly. Because both pointers start at `head`, when the list has an even number of nodes, `slow` stops at the second middle node.

## Algorithm

Initialize:

```python
slow = head
fast = head
```

Then move through the list while `fast` can still move two steps:

```python
while fast and fast.next:
    slow = slow.next
    fast = fast.next.next
```

When the loop ends, return:

```python
slow
```

For `[1,2,3,4,5]`:

| Step | `slow` | `fast` |
|---|---:|---:|
| Start | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |

Now `fast.next` is `None`, so the loop stops.

Return `slow`, which is node `3`.

For `[1,2,3,4,5,6]`:

| Step | `slow` | `fast` |
|---|---:|---:|
| Start | 1 | 1 |
| 1 | 2 | 3 |
| 2 | 3 | 5 |
| 3 | 4 | None |

Now `fast` is `None`, so the loop stops.

Return `slow`, which is node `4`.

## Correctness

At the start, both `slow` and `fast` point to the head.

During each loop iteration, `slow` moves one node and `fast` moves two nodes.

Therefore, after `k` iterations:

```text
slow has moved k steps
fast has moved 2k steps
```

The loop continues only while `fast` and `fast.next` both exist. This means `fast` can safely move two steps.

When the loop stops, `fast` has reached the end of the list or moved past the last node.

At that time, `slow` has moved half as many steps as `fast`.

So `slow` points to the middle node.

For an odd number of nodes, this is the unique middle node.

For an even number of nodes, this is the second middle node, because `slow` advances once more when `fast` moves from the second-to-last node to `None`.

Thus, the algorithm returns exactly the node required by the problem.

## Complexity

| Metric | Value | Why |
|---|---|---|
| Time | `O(n)` | We visit each node at most once through pointer movement |
| Space | `O(1)` | We only store two pointers |

## Implementation

```python
# 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]:
        slow = head
        fast = head

        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        return slow
```

## Code Explanation

We start both pointers at the first node:

```python
slow = head
fast = head
```

The `slow` pointer tracks the candidate middle node.

The `fast` pointer checks how far we are from the end.

The loop condition is:

```python
while fast and fast.next:
```

This ensures `fast.next.next` is safe to access.

Inside the loop:

```python
slow = slow.next
fast = fast.next.next
```

`slow` moves one step.

`fast` moves two steps.

When `fast` can no longer move two steps, the list has been fully measured by the fast pointer.

At that point, `slow` is at the middle node, so we return it:

```python
return slow
```

## Testing

Helper code for local testing:

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

def build_list(values):
    dummy = ListNode()
    curr = dummy

    for value in values:
        curr.next = ListNode(value)
        curr = curr.next

    return dummy.next

def to_list(head):
    values = []

    while head:
        values.append(head.val)
        head = head.next

    return values
```

Tests:

```python
def run_tests():
    s = Solution()

    head = build_list([1, 2, 3, 4, 5])
    assert to_list(s.middleNode(head)) == [3, 4, 5]

    head = build_list([1, 2, 3, 4, 5, 6])
    assert to_list(s.middleNode(head)) == [4, 5, 6]

    head = build_list([1])
    assert to_list(s.middleNode(head)) == [1]

    head = build_list([1, 2])
    assert to_list(s.middleNode(head)) == [2]

    head = build_list([1, 2, 3])
    assert to_list(s.middleNode(head)) == [2, 3]

    print("all tests passed")

run_tests()
```

Test meaning:

| Test | Why |
|---|---|
| `[1,2,3,4,5]` | Odd length list |
| `[1,2,3,4,5,6]` | Even length list, return second middle |
| `[1]` | Minimum list size |
| `[1,2]` | Smallest even length case |
| `[1,2,3]` | Small odd length case |