DAY 95 - Finding the middle of linked list

Hello Guys! This is day 95 and we are going to solve another problem using Tortoise And Hare Algorithm. In case you don't know it, check out my previous article on it.

Analyzing the Middle of a Linked List

The problem at hand involves finding the middle node of a linked list. It's a famous question often encountered in coding interviews. Let's break down the problem, understand the approach, and perform a dry run with an example to understand it better

Problem Statement: Middle of a Linked List

You are given a singly linked list, and you need to find the middle node of the list. If the list has an even number of nodes, return the second middle node.

The Approach

Before diving into the code, let's understand the intuition behind the approach.

• We can use a classic technique known as the "two-pointer" or "tortoise and hare" approach to efficiently find the middle of the linked list.

• We initialize two pointers, slow and fast, both initially pointing to the head of the list.

• The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.

• When the fast pointer reaches the end of the list (i.e., fast or fast->next becomes nullptr), the slow pointer will be at the middle of the list.

• This is because the fast pointer covers twice the distance in the same time it takes for the slow pointer to traverse the list once.

Example Dry Run

Let's perform a dry run with an example linked list to see how this approach works.

Consider the linked list: 1 -> 2 -> 3 -> 4 -> 5

1. Initially, both slow and fast point to the head, which is 1.

2. In the first iteration, slow moves to 2, and fast moves to 3.

3. In the second iteration, slow moves to 3, and fast moves to 5.

4. In the third iteration, slow stays to 3, and fast reaches the end of the list, which is nullptr.

5. Since fast is now nullptr, we stop the loop, and the slow pointer points to the middle node, which is 3.

The Code

Here's the code to find the middle node of a linked list:

ListNode* middleNode(ListNode* head) {
    ListNode* slow = head;
    ListNode* fast = head;

    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
    }

    return slow;
}

Time Complexity: O(N)
Space Complexity: O(1)