07-03-24 Middle of the Linked List

Problem Statement

Given the head of a singly linked list, we are tasked with returning the middle node of the linked list. If there are two middle nodes, we need to return the second middle node.

Example Scenarios:

Consider a couple of examples to better understand the problem:

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.

Approach 1

To find the middle node of a singly linked list efficiently, we can use the following approach:

1. Initialize two pointers, slow and fast, both pointing to the head of the linked list.
2. Move the fast pointer twice as fast as the slow pointer. This way, when the fast pointer reaches the end of the list, the slow pointer will be at the middle node.
3. Traverse the list until the fast pointer reaches the end. During each iteration, move the slow pointer one step forward and the fast pointer two steps forward.
4. Once the fast pointer reaches the end of the list (i.e., fast reaches nullptr), the slow pointer will be pointing to the middle.

Code (C++)

 #include <iostream>

struct ListNode {
    int val;
    ListNode* next;
    ListNode(int x) : val(x), next(nullptr) {}
};

ListNode* findMiddleNode(ListNode* head) {
    if (head == nullptr || head->next == nullptr)
        return head; // Edge case: List has 0 or 1 node

    ListNode* slow = head;
    ListNode* fast = head;

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

    return slow;
}

int main() {
    // Example 1
    ListNode* head1 = new ListNode(1);
    head1->next = new ListNode(2);
    head1->next->next = new ListNode(3);
    head1->next->next->next = new ListNode(4);
    head1->next->next->next->next = new ListNode(5);
    ListNode* middle1 = findMiddleNode(head1);
    std::cout << "Middle node value (Example 1): " << middle1->val << std::endl;

    // Example 2
    ListNode* head2 = new ListNode(1);
    head2->next = new ListNode(2);
    head2->next->next = new ListNode(3);
    head2->next->next->next = new ListNode(4);
    head2->next->next->next->next = new ListNode(5);
    head2->next->next->next->next->next = new ListNode(6);
    ListNode* middle2 = findMiddleNode(head2);
    std::cout << "Middle node value (Example 2): " << middle2->val << std::endl;

    return 0;
}

Output

Middle node value (Example 1): 3
Middle node value (Example 2): 4

Complexity Analysis

Time Complexity: O(n), where n is the number of nodes in the linked list.

• The fast pointer traverse the entire list, reaching the end. However, it moves twice as fast as the slow pointer.
• Therefore, the time complexity is O(n/2), which simplifies to O(n)

Space Complexity: O(1)

• We are using only two pointers, regardless of the size of the linked list.
• Thus, the space complexity is O(1), which means it's constant space complexity.