Grind 75 - 22 - Middle of the Linked List

LeetCode Problem Number: 876

Difficulty Level: Easy

Question: 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.

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

Questions to be Asked to the Interviewer

• Is the linked list always non-empty?
• If there are two middle nodes, do we always return the second one?
• What should be returned if the linked list is empty?

Edge Cases for This Problem

• If the linked list has only one node, the same node is the middle.
• If there are two nodes, the second node is considered the middle.

Available Approaches to Solve this Problem

1. Using Two Passes: First pass to find the length of the linked list, and second pass to find the middle node.
2. Using Slow and Fast Pointers: Initialize two pointers, where one moves one step at a time, and the other moves two steps. When the fast pointer reaches the end, the slow pointer will be at the middle.

Approach to Solve this Problem

I'll use the second approach using slow and fast pointers as it is more efficient.

Algorithm and Data Structure:

• Algorithm: Two Pointers
• Data Structure: Singly Linked List

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


def middleNode(head: ListNode) -> ListNode:
? ? slow = fast = head
? ? while fast and fast.next:
? ? ? ? slow = slow.next
? ? ? ? fast = fast.next.next
? ? return slow
        

Explain the Solution to a Non-Programmer

• Imagine you and your friend are on a racetrack.
• You both start at the beginning, but your friend runs twice as fast as you.
• When your friend reaches the end, you will be at the middle of the track.
• This is what we do with the linked list. We have two pointers (you and your friend), one moves twice as fast, so when it reaches the end, the other is at the middle of the list.

Code in Detail :

• Line 1-3: Defines a class ListNode to represent a node in the linked list.
• Line 5: Defines the function middleNode that takes the head of the linked list as an argument.
• Line 6: Initializes two pointers, slow and fast, both pointing at the head of the linked list.
• Line 7: A loop that continues as long as fast is not at the end and fast.next is not at the end. This ensures that the fast pointer can move two steps.
• Line 8: Moves the slow pointer one step forward in the linked list.
• Line 9: Moves the fast pointer two steps forward in the linked list.
• Line 10: Returns the slow pointer, which now points to the middle of the linked list.

The idea is to keep moving the slow pointer one step at a time and the fast pointer two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle of the linked list.

Pattern of this Problem

This problem falls under the pattern of using two pointers (in this case, "slow" and "fast" pointers) to traverse a data structure (linked list) at different speeds. This pattern is often useful when trying to locate specific elements or characteristics in a data structure, such as the middle element in this case.

Big O Notation:

• Time Complexity: The time complexity of this algorithm is O(n)- O(n), where n is the number of elements in the linked list. This is because we're traversing the linked list once, with the fast pointer moving through the entire list and the slow pointer moving through half.
• Space Complexity: The space complexity is O(1) - O(1) since we are using only a constant amount of extra space (the two pointers), irrespective of the input size.

Points to Remember to Solve this Problem in the Future

• The use of two pointers with different speeds to find the middle element.
• Always check for null pointers (e.g., the fast pointer's next element) to avoid runtime errors.
• Understanding how the two-pointer technique works in general can be applied to various other problems.

Code Line by Line with Some Sample Data

Suppose the linked list is 1 → 2 → 3 → 4 → 5.

• Line 6: Initialize slow and fast to the head (1).
• Line 7-9: Move slow to 2 and fast to 3.
• Line 7-9: Move slow to 3 and fast to 5.
• Line 7-9: Move slow to 4 and fast to None (end of the list).
• Line 10: Return slow, which is at node 4.

Key Syntax Used in this Solution:

• Defining a Class: class ListNode: to define the linked list node.
• While Loop: while fast and fast.next: to continue the loop as long as conditions are met.
• Accessing Next Element: Using .next to access the next element in the linked list.

The next problem is

Maximum Depth of Binary Tree