Problem: Middle of the Linked List

Description

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:

  1. Input: head = [1,2,3,4,5]
    Output: [3,4,5]
    Explanation: The middle node of the list is node 3.

  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.

Solution in Python


class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        temp = head
        while temp and temp.next:
            head = head.next
            temp = temp.next.next

        return head

Explanation:

The solution uses the two-pointer technique, often known as the “slow and fast pointer” method. The temp pointer moves twice for every single move of the head pointer. By the time temp reaches the end of the list, the head pointer will be at the middle of the list. This approach effectively halves the traversal time, making it an efficient way to find the middle of a linked list.

LeetCode