algoadvance

You are 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.

Clarifying Questions

1. Input Constraints: What are the constraints on the number of nodes in the linked list?
   • The number of nodes in the list is in the range [1, 100].
2. Node Structure: What does a node of the linked list look like?
   • Each node has an int value and a next reference to the next node in the list, or null if it is the last node.
3. Return Type: Should the function return the entire list starting from the middle node or just the middle node’s value?
   • The function should return the entire list starting from the middle node.
4. Edge Cases: How do we handle edge cases like a single-node list or an even number of nodes?
   • For a single-node list, the same node should be returned.
   • For an even number of nodes, the second middle node should be returned.

Code

Here is the code to find the middle of the linked list:

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def middleNode(head: ListNode) -> ListNode:
    slow = fast = head
    
    # Traverse the list with two pointers at different speeds
    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next
        
    return slow

Strategy

The strategy to solve this problem uses the Two Pointers approach:

1. Two Pointers Initialization:
   • Initialize two pointers, slow and fast, both pointing to the start of the linked list.
2. Traversal:
   • Move the slow pointer one step at a time.
   • Move the fast pointer two steps at a time.
3. Finding the Middle:
   • By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle of the list.
   • This works because the fast pointer moves twice as fast as the slow pointer, so when fast reaches the end, slow will have covered half the distance.
4. Edge Cases:
   • If the list has only one node, slow will already be at the middle (and start).
   • If the list has an even number of nodes, slow will end up at the second middle node when fast reaches the end.

Time Complexity

The time complexity of this approach is O(n), where n is the number of nodes in the linked list.

• Reason: Both slow and fast pointers traverse the list, but since fast moves twice as fast, the loop will terminate after n/2 iterations, which is still O(n).

The space complexity is O(1) because we are using only a fixed amount of extra space (i.e., the two pointers).

Summary

• Two Pointers technique efficiently finds the middle node on a single pass through the list.
• It handles both odd and even sized lists correctly.
• The solution is optimal with O(n) time complexity and O(1) space complexity.

Try our interview co-pilot at AlgoAdvance.com

• Got blindsided by a question you didn’t expect?

• Spend too much time studying?

• Or simply don’t have the time to go over all 3000 questions?