Middle Of Linked List LeetCode 876
Step-by-Step Guide to Solving LeetCode 876: Middle of the Linked List
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
Initialization:
let slowPointer = head; let fastPointer = head;
We initialize two pointers,
slowPointer
andfastPointer
, both pointing to the head of the linked list.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
andfastPointer.next
are notnull
. This ensures that the fast pointer can move two steps ahead without encounteringnull
.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
).
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
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.
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.