Middle of the Linked List DSA Solution - Study Chapter | QuizMaker

Middle of the Linked List explained with brute force, optimized fast/slow pointers, dry run, edge cases, complexity, and Python, C++, Java code.

Read: 9m
Type: Chapter
Access: Free

Course

DSA Course: Interview Patterns and Problem Solving

Topic

Module 5: Linked List

Learning Outcome

After this lesson, you should be able to use fast and slow pointers to find the middle node in one pass.

Problem Statement

Given the head of a singly linked list, return the middle node. If there are two middle nodes, return the second middle node.

Input	Output	Why
`1 -> 2 -> 3 -> 4 -> 5`	`3`	3 is the middle node.
`1 -> 2 -> 3 -> 4 -> 5 -> 6`	`4`	There are two middles, so return the second.

Brute Force Approach

Count the number of nodes, then walk again to index n / 2.

This is correct, but it needs two passes through the list.

Optimized Approach

Move slow one step and fast two steps. When fast reaches the end, slow has moved half as many steps, so it is at the middle.

Exact Pseudocode

slow = head
fast = head
while fast is not null and fast.next is not null:
  slow = slow.next
  fast = fast.next.next
return slow

Reference Code

class Solution:
    def middleNode(self, head):
        slow = head
        fast = head

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

        return slow

class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        ListNode* slow = head;
        ListNode* fast = head;

        while (fast != nullptr && fast->next != nullptr) {
            slow = slow->next;
            fast = fast->next->next;
        }

        return slow;
    }
};

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }

        return slow;
    }
}

Sample Dry Run

Step	slow	fast	Meaning
Start	1	1	Both at head
1	2	3	Fast moved twice as far
2	3	5	Slow reaches middle
Stop	3	null after next move check	Return slow

Complexity

Measure	Value	Reason
Time	O(n)	The list is traversed once.
Space	O(1)	Only two pointers are used.

Edge Cases

Single-node list returns the head.
Even-length list returns the second middle.
Empty list if platform allows it.

Interview Checklist

Move fast two steps and slow one step.
Use the loop condition fast != null and fast.next != null.
Know whether the problem asks for first or second middle.

FAQs

Why does slow end at the middle?

Because fast moves twice as quickly. When fast covers the full list, slow covers half.

Why does this return the second middle for even length?

The loop continues while fast can move two steps, causing slow to advance to the second middle.

What is the core pattern?

Fast and slow pointers.