Middle Of Linked List LeetCode 876

In this blog post, we'll explore an efficient way to find the middle node of a singly linked list using JavaScript. We'll dive into the code and understand the logic behind it step by step.

Link:https://leetcode.com/problems/middle-of-the-linked-list/

Problem Statement

Given a non-empty, singly linked list with head node head, return a middle node of the linked list.

If there are two middle nodes, return the second middle node.

Approach

We can solve this problem using two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time while the fast pointer moves two steps at a time. By the time the fast pointer reaches the end of the list, the slow pointer will be at the middle node.

Code Explanation

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

var middleNode = function(head) {
    let slowPointer = head;
    let fastPointer = head;

    while(fastPointer !== null && fastPointer.next !== null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }

    return slowPointer;
};

Let's break down the code step by step.

Step-by-Step Explanation

1. Initialization:

    let slowPointer = head;
    let fastPointer = head;
   

   We initialize two pointers, slowPointer and fastPointer, both pointing to the head of the linked list.

2. Traversal:

    while(fastPointer !== null && fastPointer.next !== null){
        slowPointer = slowPointer.next;
        fastPointer = fastPointer.next.next;
    }
   

   We use a while loop to move through the linked list. The loop continues until the fast pointer reaches the end of the list.

   • Condition: The loop runs as long as fastPointer and fastPointer.next are not null. This ensures that the fast pointer can move two steps ahead without encountering null.

   • Movement:

       slowPointer = slowPointer.next;
       fastPointer = fastPointer.next.next;
     

     Inside the loop, we move the slow pointer one step forward (slowPointer.next) and the fast pointer two steps forward (fastPointer.next.next).

3. Returning the Middle Node:

    return slowPointer;
   

   Once the fast pointer reaches the end of the list, the slow pointer will be at the middle node. We return the slow pointer as the result.

Why This Approach Works

The fast pointer moves twice as fast as the slow pointer. Therefore, by the time the fast pointer reaches the end of the list, the slow pointer will have covered half the distance. This ensures that the slow pointer is positioned at the middle node.

Edge Cases

1. Single Node: If the linked list has only one node, the function will return that node as both pointers will initially point to the same node.

2. Even Number of Nodes: The function will return the second middle node if the linked list has an even number of nodes. This is because the fast pointer will skip over the middle nodes, making the slow pointer land on the second middle node.

Conclusion

Finding the middle node of a linked list using the two-pointer technique is an efficient approach with a time complexity of O(n) and a space complexity of O(1). This method is widely used in various linked list problems due to its simplicity and efficiency.