If you guys study a linked list or work with a linked list, one common task is to find the middle node.

In this article, we will explore different approaches to solve this question and implement their solutions in JavaScript. We will also analyze the time and space complexities of each approach. By the end of this article, you will have a comprehensive understanding of solving this problem. But before that let’s see the problem statement.

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.

Approach 1: Count The Nodes

This approach involves counting the number of nodes in the linked list.

1. First, iterate through the entire list and count the number of nodes.

2. Then, iterate again up to the middle node (count/2), starting from the head.

// ES6 Arrow Function
const middleNode = head => {
    let count = 0;
    let curr = head;

    while(curr !== null) {
        count++;
        curr = curr.next;
    }

    curr = head;
    for(let i = 0; i < Math.floor(count / 2); i++) {
        curr = curr.next;
    }

    return curr;
}

Time Complexity: O(N)

N is the number of nodes in the linked list. Firstly, we are going through each node to find the length of the linked list which takes O(N) time. Then we are iterating again till N/2 nodes only so the total complexity is linear.

Space Complexity: O(1)

Since we are not using any extra space, the space complexity is constant.

Approach 2: Two Pointers (Slow and Fast Pointers)

1. In this approach, initially, both pointers point to the head of the linked list.

2. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time.

3. When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle node.

// ES6 Arrow Function
const middleNode = head => {
    let slow = head;
    let fast = head;

    while(fast !== null && fast.next !== null) {
        slow = slow.next;
        fast = fast.next.next;
    }

    return slow;
}

Time Complexity: O(N)

We traverse the linked list using two pointers: a slow pointer and a fast pointer. The slow pointer moves one node at a time, while the fast pointer moves two nodes at a time. Since the fast pointer traverses the list twice as fast as the slow pointer, it reaches the end of the list after approximately N/2 iterations. Therefore, the overall time complexity is O(N/2), which can be simplified to O(N)

Space Complexity: O(1)

We are not using any additional data structures that grow with the size of the input. We only need two pointers (slow and fast) to keep track of the nodes in the linked list. These pointers require a constant amount of space regardless of the size of the linked list.

And there you have it guys! We’ve explored two different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem - Leetcode 876