043.md

876. Middle of the Linked List

Difficulty: 🟢 Easy

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.

Examples:

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.

Constraints:

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

Solutions

O(n) solution in Python3

# 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]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

The given solution uses a two-pointer approach to find the middle node of the linked list. The two pointers are named slow and fast, and they initially point to the head of the linked list.

The algorithm works as follows:

1. Initialize both slow and fast pointers to the head of the linked list.
2. Move slow one step forward and fast two steps forward in each iteration until fast reaches the end of the list or the next of fast becomes None.
3. When fast reaches the end of the list, slow will be pointing to the middle node.

Finally, the algorithm returns the slow pointer as the middle node.

Analysis of Time and Space Complexity

The time complexity of this algorithm is O(N), where N is the number of nodes in the linked list. In the worst case, the fast pointer will traverse the entire list, and since it moves twice as fast as the slow pointer, it will take approximately N/2 iterations to reach the end of the list.

The space complexity of the algorithm is O(1) since it only uses a constant amount of extra space for the slow and fast pointers.

Summary

The given solution efficiently finds the middle node of a singly linked list using a two-pointer approach. It has a time complexity of O(N) and a space complexity of O(1), making it an optimal solution for the problem at hand.

NB: If you want to get community points please suggest solutions in other languages as merge requests.