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

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

Example 2

list

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

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

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

Leetcode: link