🖕876. Middle of the Linked List

Easy | Grind 75 | November 1st Tuesday, 2022

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

• The number of nodes in the list is in the range [1, 100].

• 1 <= Node.val <= 100

Example 1

Example 2

SOLUTION

Given that we need to find the middle, it is vital to know the length of the linked list. We will find the length of the linked list by iterating over it once. We then divide the length by 2 to find the half (we will call it N). Finally, we will iterate N times in the original linked list to get to the middle of the list.

Alternate way(not implemented): There is also a way to find the middle without knowing the length of the linked list. We can have two-pointers (slow and fast). The fast pointer is always two steps ahead of the slow pointer. Therefore, when the fast pointer is at the end of the linked list, the slow pointer is in the middle.

# 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: Optional[ListNode]) -> Optional[ListNode]:
        # iterate this to find the length of the linked list
        iterator = head
        count = 0
        while iterator != None: 
            iterator = iterator.next
            count += 1
        
        # middle = half
        half = count // 2
        
        # iterate until the half
        for i in range(0,half): 
            head = head.next
        
        return head
    

TIME AND SPACE COMPLEXITY

TIME: O(n) where n is the number of nodes. During the first iteration to calculate the length, we traverse n times. And then later to return the middle node, we traverse n/2 times. In total we traverse n + n/2 times.

SPACE: O(1) Space is constant. Regardless of the size of the linked list, we just need one variable that stores an integer.