We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

Middle of the Linked List

Number: 908

Difficulty: Easy

Paid? No

Companies: Google, Amazon, Microsoft, Meta, tcs, Intuit, Bloomberg, Apple, Adobe, Uber, Salesforce, Walmart Labs

Problem Description

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.

Key Insights

Use two pointers (slow and fast) to traverse the list.
The fast pointer moves two steps at a time while the slow pointer moves one step.
When the fast pointer reaches the end, the slow pointer will be at the middle node.
This approach naturally handles both odd and even lengths of the list.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes in the list.
Space Complexity: O(1), constant extra space.

Solution

The solution uses the two-pointer technique:

Initialize two pointers, slow and fast, at the head.
Traverse the list, moving slow by one step and fast by two steps during each iteration.
When fast reaches the end or has no next node, slow will be at the middle.
Return the slow pointer (the middle node).

This strategy ensures linear time complexity and constant space, efficiently finding the middle node even for lists with an even number of elements.

Code Solutions

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # Initialize slow and fast pointers at the head of the list
        slow = head
        fast = head
        # Loop until fast reaches the end of the list
        while fast and fast.next:
            # Move slow pointer one step
            slow = slow.next
            # Move fast pointer two steps
            fast = fast.next.next
        # When loop ends, slow pointer points to the middle node
        return slow

← Back to All Questions