LL 5 - Middle of the Linked List (Tortoise Hare)

Problem Statement

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. (link)

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.

Solution

Brute force Approach

Initially, determine the total count of elements within the linked list. Next, iterate through the linked list again up to half of the total count. Finally, return the pointer directly.

Time - O(n+n/2)

Space - O(1)

class Solution {
    public ListNode middleNode(ListNode head) {
        int totalElements = 0;
        ListNode temp = head;

        while(temp!=null){
            totalElements += 1;
            temp = temp.next;
        }

        temp = head;

        for(int i=0; i<totalElements/2; i++)
            temp = temp.next;

        return temp;
    }
}

Optimal Approach - Tortise & Hare (Slow & Fast pointers)

Utilize two pointers, ptr1 and ptr2. Proceed to traverse the linked list such that ptr1 increments by 1 and ptr2 advances by 2 steps. Consequently, when ptr2 reaches the final element or null, ptr1 will precisely indicate the middle element. This is because if ptr2 covers a distance of n, ptr1 will cover a distance of n/2.

If ptr2 reaches null, it indicates that the linked list length is even.

If ptr2 is on the last element, it indicates that the linked list length is odd.

The iteration can be halted when ptr2 reaches the last element or becomes null, and ptr1 can be returned as the result.

class Solution {
    public ListNode middleNode(ListNode head) {
        ListNode ptr1 = head;
        ListNode ptr2 = head;

        while(ptr2!=null && ptr2.next!=null){
            ptr1 = ptr1.next;
            ptr2 = ptr2.next.next;
        }
        return ptr1;
    }
}