Leetcode – Middle of the Linked List Solution in Python

Spread the love

Linked lists are among the primary data structures that one often encounters in computer science. They offer a dynamic approach to storing data in a linear fashion, where elements, often referred to as “nodes,” point to the next element in the sequence. One popular problem on Leetcode, the Middle of the Linked List problem, provides a fundamental challenge around linked lists. This article offers a comprehensive exploration of this problem, discussing insights, possible solutions, and their implementations in Python.

Problem Statement

Given a non-empty, singly linked list with head node head, return a middle node of the linked list.

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

Constraints:

  • The number of nodes in the given list will be between 1 and 100.

Examples:

  1. Input: [1,2,3,4,5] Output: Node with value 3 Explanation: The middle node of the list is Node 3.
  2. Input: [1,2,3,4,5,6] Output: Node with value 4 Explanation: There are two middle nodes, 3 and 4. We return the second one.

Analysis

To solve this problem, one might initially consider traversing the linked list to determine its length and then traversing it again to find the middle element. However, this approach requires two traversals, which can be inefficient.

A more efficient approach would be to find the middle node with a single traversal. This can be achieved by employing two pointers technique.

Solution Strategy: Two Pointers

The idea here is to use two pointers:

  1. Slow Pointer: This moves one step at a time.
  2. Fast Pointer: This moves two steps at a time.

By the time the fast pointer reaches the end of the linked list, the slow pointer will be halfway through, landing on the middle node.

Python Code:

First, let’s represent the structure of a node in the linked list:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

Now, let’s move to the solution:

class Solution:
    def middleNode(self, head: ListNode) -> ListNode:
        # Initialize both pointers to the head of the linked list
        slow = head
        fast = head

        # Move the fast pointer two steps and the slow pointer one step at a time
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next

        # When the fast pointer reaches the end, the slow pointer will be at the middle
        return slow

Complexity Analysis

  1. Time Complexity: Since we traverse the linked list only once, the time complexity is linear, or O(N), where N is the number of nodes in the linked list.
  2. Space Complexity: We use only a constant amount of space (two pointers), regardless of the input size. Thus, the space complexity is O(1).

Conclusion

The Middle of the Linked List problem elegantly demonstrates the power of the two-pointer technique. While the naive solution would have involved two traversals of the linked list, the optimized approach completes the task in a single traversal, making it more efficient.This problem serves as a gentle introduction to the many intricacies of linked list operations and showcases how innovative thinking can lead to optimized solutions. It’s a testament to the importance of understanding foundational data structures like linked lists and mastering techniques like the two-pointer strategy to tackle a wide range of problems efficiently.

Leave a Reply