876 Middle of the Linked List - Easy
Problem:
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.
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
Problem Analysis:
1. High Level Strategy:
The solution employs the concept of slow and fast pointers to find the middle node of the linked list. Initially, both pointers, slow
and fast
, are set to the head of the linked list. The slow
pointer moves one node at a time, while the fast
pointer moves two nodes at a time. By the time the fast
pointer reaches the end of the list, the slow
pointer will be at the middle node. This is due to the relative speeds of the two pointers - the fast
pointer moves twice as fast as the slow
pointer, so when the fast
pointer reaches the end, the slow
pointer will be at the midpoint.
2. Complexity:
- Time Complexity: The algorithm traverses the linked list once, with the
fast
pointer moving twice as fast as theslow
pointer. Hence, the time complexity is O(n), where n is the number of nodes in the linked list. - Space Complexity: The algorithm uses only a constant amount of extra space for two pointers (
slow
andfast
), regardless of the size of the input linked list. Thus, the space complexity is O(1).
Solutions:
# 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
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow