> For the complete documentation index, see [llms.txt](https://leetcode.realtemirov.uz/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://leetcode.realtemirov.uz/problems/876.-middle-of-the-linked-list.md).

# 876. Middle of the Linked List

🟩 Easy

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.

## Example 1

![list](https://assets.leetcode.com/uploads/2021/07/23/lc-midlist1.jpg)

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

## Example 2

![list](https://assets.leetcode.com/uploads/2021/07/23/lc-midlist2.jpg)

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

## Solution

My Solution

```go
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    slow, fast := head, head

    for fast != nil && fast.Next != nil{
        slow = slow.Next
        fast = fast.Next.Next
    }

    return slow
}
```

Optimal Solution (Two Pass)

```go
func middleNode(head *ListNode) *ListNode {
    length := 0
    curr := head
    
    // First pass: count nodes
    for curr != nil {
        length++
        curr = curr.Next
    }
    
    // Second pass: find middle
    middle := length / 2
    curr = head
    for i := 0; i < middle; i++ {
        curr = curr.Next
    }
    
    return curr
}
```

### Approach Analysis

This problem demonstrates two elegant approaches to find the middle node:

1. Fast & Slow Pointer (Your Solution):
   * Uses two pointers moving at different speeds
   * Fast moves twice as fast as slow
   * When fast reaches end, slow is at middle
   * Single pass, elegant solution
2. Two Pass Approach (Alternative):
   * First pass counts total nodes
   * Second pass moves to middle
   * More intuitive but less efficient
   * Good for learning linked lists

### Visualization of Both Approaches

#### Fast & Slow Process (Your Solution)

```
Initial State:
1 -> 2 -> 3 -> 4 -> 5
SF

Step 1:
1 -> 2 -> 3 -> 4 -> 5
     S    F

Step 2:
1 -> 2 -> 3 -> 4 -> 5
          S         F

Final (F reaches end, S at middle):
1 -> 2 -> 3 -> 4 -> 5
          S         F
```

#### Two Pass Process

```
First Pass (Counting):
1 -> 2 -> 3 -> 4 -> 5
^    ^    ^    ^    ^
1    2    3    4    5 nodes

Second Pass (Finding Middle):
1 -> 2 -> 3 -> 4 -> 5
          ^
        middle (5/2 = 2 steps)
```

### Complexity Analysis

#### Fast & Slow Solution (Your Solution)

* Time: O(n)
  * Single pass through list
  * Fast pointer moves n/2 times
  * Most efficient approach
* Space: O(1)
  * Only two pointers
  * Constant extra space
  * No additional data structures

#### Two Pass Solution

* Time: O(n)
  * First pass: n steps to count
  * Second pass: n/2 steps to middle
  * Total: 1.5n steps
* Space: O(1)
  * Only two variables
  * Counter and current pointer
  * Constant extra space

### Why Fast & Slow Works

1. Mathematical Foundation:
   * Fast pointer moves at 2x speed
   * When fast reaches end
   * Slow has covered exactly half
   * Perfect for middle finding
2. Handling Edge Cases:
   * Works for odd and even lengths
   * Automatically finds second middle
   * No special case handling needed
   * Naturally handles single node

### When to Use

1. Fast & Slow Pattern Best For:
   * Finding middle elements
   * Cycle detection
   * Pattern finding in sequences
   * Distance-based problems
2. Two Pass Approach When:
   * Need total length anyway
   * Learning linked lists
   * Code readability priority
   * Teaching algorithms

### Common Patterns & Applications

1. Related Problems:
   * Linked List Cycle
   * Linked List Cycle II
   * Happy Number
   * Find the Duplicate Number
2. Key Techniques:
   * Two-pointer technique
   * Floyd's Cycle Finding
   * Runner technique
   * Distance calculations

### Interview Tips

1. Solution Highlights:
   * Single pass efficiency
   * No extra space needed
   * Works for all list sizes
   * Elegant mathematical property
2. Common Pitfalls:
   * Forgetting fast.Next check
   * Off-by-one in two-pass
   * Not handling edge cases
   * Wrong middle for even length
3. Testing Approach:
   * Empty list
   * Single node
   * Two nodes
   * Odd length list
   * Even length list
4. Follow-up Questions:
   * Handle circular lists?
   * Find first middle instead?
   * Return index instead of node?
   * Optimize for repeated calls?

![result](/files/lxowZeBW8BDRjnGegSGl)

Leetcode: [link](https://leetcode.com/problems/middle-of-the-linked-list/description/)