# 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/)


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://leetcode.realtemirov.uz/problems/876.-middle-of-the-linked-list.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.