876. Middle of the Linked List - Leetcode Solution

LeetCode problem

Solution code

💡 Step-by-Step Thought Process

Understand the problem: Find the middle node of a singly linked list; if there are two middle nodes, return the second one.
Initialize two pointers, slow and fast, both starting at the head of the list.
While fast and fast.next are not None:
- Move fast two steps forward (fast.next.next).
- Move slow one step forward (slow.next).
Return slow as the middle node, as slow will be at the middle when fast reaches the end.

Code Solution

class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow = head
        fast = head

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

        return slow

# Time Complexity: O(n)
# Space Complexity: O(1)

#include <iostream>
using namespace std;


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

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

        return slow;
    }
};

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

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

        return slow;
    }
}

var middleNode = function(head) {
    let slow = head;
    let fast = head;

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

    return slow;
};

Detailed Explanation

Understanding the Problem: Middle of the Linked List

The “Middle of the Linked List” problem asks us to return the middle node of a singly linked list. If the list has an even number of nodes, we are required to return the second middle node.

Example:

Input: 1 → 2 → 3 → 4 → 5
Output: Node with value 3
Input: 1 → 2 → 3 → 4 → 5 → 6
Output: Node with value 4

Why This Problem Matters

This problem introduces one of the most elegant applications of the two-pointer technique — a method used in many advanced linked list problems. Understanding how to find midpoints with pointers builds a foundation for more complex challenges like palindrome checking, cycle detection, and list reordering.

Optimal Approach: Slow and Fast Pointer Technique

The best way to find the middle node of a singly linked list in a single pass is to use two pointers:

Slow pointer: moves one node at a time
Fast pointer: moves two nodes at a time

When the fast pointer reaches the end of the list, the slow pointer will be at the midpoint.

Steps:

Initialize both slow and fast pointers at the head of the list.
Traverse the list with the following loop:
- While fast != null and fast.next != null:
Once the loop ends, slow will be pointing to the middle node.
Return slow.

Example Walkthrough

Input: 1 → 2 → 3 → 4 → 5
Iteration steps:

slow = 1, fast = 1
slow = 2, fast = 3
slow = 3, fast = 5
fast.next is null → stop
Return slow → node 3

For even-length list: 1 → 2 → 3 → 4 → 5 → 6 → returns node 4 (the second middle).

Time and Space Complexity

Time Complexity: O(n), where n is the number of nodes. Each node is visited at most once.
Space Complexity: O(1), as we use only two pointers.

Edge Cases to Consider

Single-node list → return that node
Two-node list → return the second node
Empty list → depending on constraints, return null or handle safely

Conclusion

The “Middle of the Linked List” problem is a classic use of the slow and fast pointer technique. It's a clean and efficient solution that runs in linear time without needing to count nodes or use extra memory. Mastering this strategy will benefit you in numerous other linked list-related problems.

NEW!Need help landing software roles? 💡

AlgoMap.io