Middle of the Linked List

This is one of the most popular Linked List interview questions because it introduces the powerful Fast and Slow Pointer Pattern.

The pattern appears in many advanced problems such as:

• Detect Cycle in Linked List
• Find Starting Point of Cycle
• Happy Number
• Palindrome Linked List

Let's understand why it works.

---

Problem Statement

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

Input:
1 -> 2 -> 3 -> 4 -> 5

Output:
3

Example 2

Input:
1 -> 2 -> 3 -> 4 -> 5 -> 6

Output:
4

Notice that for an even-length list, we return the second middle node.

---

Brute Force Approach

Intuition

A simple approach is:

1. Traverse the linked list and count the total number of nodes.
2. Traverse again until count / 2.
3. Return that node.

Since we need two traversals, it works but isn't the most elegant solution.

Complexity

Time Complexity  : O(N)
Space Complexity : O(1)

Brute Force Code

class Solution {
    public ListNode middleNode(ListNode head) {

        int count = 0;

        ListNode temp = head;

        while (temp != null) {
            count++;
            temp = temp.next;
        }

        temp = head;

        for (int i = 0; i < count / 2; i++) {
            temp = temp.next;
        }

        return temp;
    }
}

---

Moving Towards the Optimal Approach

Can we find the middle in a single traversal?

Instead of counting nodes first, we can use two pointers moving at different speeds.

If one pointer moves twice as fast as the other, by the time the fast pointer reaches the end, the slow pointer will naturally be standing at the middle.

This is the famous Tortoise and Hare Algorithm.

---

Optimal Approach - Fast & Slow Pointer

Maintain two pointers:

slow
fast

• slow moves one step at a time.
• fast moves two steps at a time.

When fast reaches the end:

slow

will be exactly at the middle node.

---

Visual Intuition

Initial State

1 -> 2 -> 3 -> 4 -> 5

S
F

After First Move

1 -> 2 -> 3 -> 4 -> 5

     S
          F

After Second Move

1 -> 2 -> 3 -> 4 -> 5

          S
                F

Fast reaches the end.

Slow is now pointing at the middle node.

---

Dry Run

Input

1 -> 2 -> 3 -> 4 -> 5

Initial State

slow = 1
fast = 1

Iteration 1

slow = 2
fast = 3

Iteration 2

slow = 3
fast = 5

Next Check

fast.next == null

Loop stops.

Result

return slow

3

---

Optimal Java Solution

class Solution {

    public ListNode middleNode(ListNode head) {

        ListNode fast = head;
        ListNode slow = head;

        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

---

Why This Works

Think of it this way:

slow -> 1 step
fast -> 2 steps

When the fast pointer has covered the entire linked list,

N steps

the slow pointer has covered only

N / 2 steps

which is exactly the middle position.

That's why the slow pointer ends up at the middle node.

---

Complexity Analysis

Time Complexity  : O(N)
Space Complexity : O(1)

• Single traversal of the linked list.
• No extra data structure used.

---

Key Takeaway

Whenever a Linked List problem involves:

• Finding the middle
• Detecting a cycle
• Finding cycle start
• Splitting a list

Immediately think about the Fast & Slow Pointer Pattern.

It's one of the most powerful techniques in Linked Lists and appears repeatedly in coding interviews.

---