Middle of the Linked List

Difficulty: Easy | Acceptance: 81.80% | Paid: No Topics: Linked List, Two Pointers

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
• Constraints
• Approach 1: Count Nodes
• Approach 2: Fast and Slow Pointers

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

Approach 1: Count Nodes

Intuition Traverse the entire list to count the total number of nodes, then traverse a second time to reach the middle node at index count // 2.

Steps

• Initialize a counter to 0 and a pointer to the head.
• Traverse the list to count the total number of nodes.
• Calculate the index of the middle node (total count divided by 2).
• Traverse the list again from the head until the middle index is reached.
• Return the node at that index.

# 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]:
        count = 0
        current = head
        while current:
            count += 1
            current = current.next
        
        mid_index = count // 2
        current = head
        for _ in range(mid_index):
            current = current.next
            
        return current

Complexity

• Time: O(N) — We traverse the list twice, which is linear time.
• Space: O(1) — We only use a few pointers for counting and traversal.
• Notes: Simple to implement but requires two passes over the list.

Approach 2: Fast and Slow Pointers

Intuition 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.

Steps

• Initialize two pointers, slow and fast, both pointing to the head of the list.
• Iterate while fast is not null and fast.next is not null.
• In each iteration, move slow one step forward and fast two steps forward.
• When the loop terminates, slow will be at the middle node.
• Return slow.

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

Complexity

• Time: O(N) — We traverse the list only once. The fast pointer visits every node, and the slow pointer visits half.
• Space: O(1) — Only two pointers are used regardless of the list size.
• Notes: This is the optimal approach for finding the middle node in a single pass.