Middle Of The Linked List Leetcode Problem 876 [Python Solution]

In this blog post, we will explore the LeetCode problem Middle Of The Linked List (Problem 876) and provide a Python solution for it.

This problem falls under the category of Linked List and is categorized as “Easy.” It’s a common problem often asked in coding interviews, and it’s essential to understand how to solve it efficiently.

Before we dive into the solution, let’s start with a brief problem overview.

Problem Overview

The problem statement is as follows:

Given the head of a singly linked list, you need to return the middle node of the linked list.

If there are two middle nodes, return the second middle node.

In other words, you’re given a singly linked list, and you need to find the middle node.

If the linked list has an odd number of nodes, the middle node is straightforward to determine.

However, when the linked list has an even number of nodes, you need to return the second middle node.

Let’s take a look at a couple of examples to illustrate this:

Example 1:

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

Example 2:

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.

Now that we understand the problem statement let’s discuss the constraints.

Understanding the Constraints

The problem’s constraints are essential to consider when designing our solution.

For the Middle Of The Linked List problem, we have the following constraints:

The number of nodes in the linked list is in the range [1, 100].
The values of each node (Node.val) are in the range [1, 100].

Now that we have a clear understanding of the problem and its constraints, let’s move on to the solution.

Middle of the Linked List LeetCode Problem Solution

1. Bruteforce Approach

A straightforward approach to finding the middle of a linked list is to calculate the length of the list first.

Then, using the length, we can find the middle node.

This approach involves iterating through the entire list to count the number of nodes.

Here’s a Python implementation for this approach:

def middleNode(head):
    if not head or not head.next:
        return head

    # Count the number of nodes in the linked list
    count = 0
    current = head
    while current:
        count += 1
        current = current.next

    # Find the middle node
    middle = count // 2
    current = head
    for _ in range(middle):
        current = current.next

    return current

While this approach works, it’s not the most efficient solution, especially for large linked lists.

It has a time complexity of O(n), where n is the number of nodes in the list.

We can improve this by using a more efficient approach.

2. An Efficient Approach with Two Pointers

To find the middle of a linked list more efficiently, we can use a technique called the “two-pointer” approach.

This technique involves maintaining two pointers, a slow pointer and a fast pointer, and moving them through the list at different speeds.

Here’s the Python implementation for this approach:

def middleNode(head):
    if not head or not head.next:
        return head

    slow = fast = head

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

    return slow

Let’s break down how this efficient approach works:

We initialize both slow and fast pointers to the head of the linked list.
The fast pointer moves two steps at a time, while the slow pointer moves one step at a time.
As long as the fast pointer and its next node are not null (i.e., there are more nodes to traverse), we continue moving the pointers.
When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

This approach ensures that the slow pointer reaches the middle of the linked list efficiently, with a time complexity of O(n), where n is the number of nodes in the list.

It’s a more optimal solution compared to the brute-force method.

Python Code Solution

Here’s the Python code for the efficient approach to finding the middle of a linked list:

View on GitHub ➹

def middleNode(head):
    if not head or not head.next:
        return head

    slow = fast = head

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

    return slow

Now that we have our solution, let’s analyze the time and space complexity.

Time and Space Complexity

Time Complexity: The time complexity of this efficient solution is O(n), where n is the number of nodes in the linked list.

We iterate through the list only once, making this solution highly efficient.

Space Complexity: The space complexity is O(1), which means it uses constant space.

We don’t require any additional data structures; only a few pointers are used.

Reasoning Behind Our Approach

The reasoning behind the efficient two-pointer approach lies in understanding that if we have two pointers—one slow and one fast—that move through the linked list at different speeds, we can reach the middle node when the fast pointer reaches the end.

This technique allows us to traverse the list just once, resulting in optimal time complexity.

In summary, this problem can be efficiently solved using two pointers, making it an excellent addition to your problem-solving toolkit.

Conclusion

In this blog post, we tackled the LeetCode problem Middle Of The Linked List (Problem 876) in the Linked List category.

We discussed the problem’s requirements, constraints, and provided both a brute-force and an efficient solution using the two-pointer technique.

We encourage you to practice this problem and understand the two-pointer approach, as it’s a valuable technique used in various linked list and array-related problems.

If you found this blog post helpful, please like and engage for more coding and algorithm-related content.

If you’re preparing for coding interviews, check out neatcode.io, a platform offering a wealth of free resources to help you prepare.

Feel free to comment, ask questions, make suggestions, and share this content with others who might find it beneficial.

Coding is a journey, and continuous learning is key to mastering it.

For the original question and more details, you can visit the problem on LeetCode: Middle of the Linked List.

Happy coding, and may your problem-solving skills continue to grow!