876. Middle of the Linked List
Model: qwen2.5-coder:14b
Topics: Linked List
FAANG asked: 0
Acceptance rate: 69.2%
Problem Breakdown
The problem requires finding the middle node of a singly linked list. The input is a non-empty singly linked list with a head node head. The output should be the middle node of the list. If there are two middle nodes (i.e., the list has an even number of nodes), we return the second middle node.
Inputs:
- A non-empty singly linked list with a head node
head.
Outputs:
- A ListNode object representing the middle node of the list.
Implicit Constraints or Tricky Edge Cases:
- The list can have between 1 and 100 nodes.
- If the list has an even number of nodes, return the second middle node.
Intuition
A brute-force approach would involve traversing the linked list to count the total number of nodes and then traversing again to find the middle node. This approach is inefficient because it requires two passes through the list, resulting in a time complexity of O(n).
The key insight for a better approach is to use two pointers: a slow pointer that moves one step at a time and a fast pointer that moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
Approach
- Initialize two pointers,
slowandfast, both pointing to the head of the linked list. - Traverse the list with the
fastpointer moving two steps at a time and theslowpointer moving one step at a time. - When the
fastpointer reaches the end of the list (i.e.,fastisNoneorfast.nextisNone), theslowpointer will be at the middle node. - Return the
slowpointer as the result.
This approach ensures that we only traverse the list once, achieving a time complexity of O(n) with a space complexity of O(1).
Complexity Analysis
- Time Complexity: O(n), where n is the number of nodes in the linked list. We traverse the list once.
- Space Complexity: O(1). We use only two pointers regardless of the size of the input.
Solution
# 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: ListNode) -> ListNode:
slow = fast = head
while fast and fast.next:
slow = slow.next
fast = fast.next.next
return slow
Edge Cases Handled
- Single Node List: If the list contains only one node, both
slowandfastwill point to that node, and it will be returned correctly. - Even Number of Nodes: The algorithm naturally returns the second middle node when the list has an even number of nodes by moving the
slowpointer one step further in each iteration.