Solution: Middle of the Linked List
Let's solve the Middle of the Linked List problem using the Fast and Slow Pointers pattern.
Statement
Given the head
of a singly linked list, return the middle node of the linked list. If the number of nodes in the linked list is even, there will be two middle nodes, so return the second one.
Constraints:
Let n
be the number of nodes in a linked list.
-
n
-
node.data
head
NULL
Solution
So far, you have probably brainstormed some approaches and have an idea of how to solve this problem. Let’s explore some of these approaches and figure out which one to follow based on considerations such as time complexity and any implementation constraints.
Naive approach
In the naive approach, we use an external array to store the elements of the linked list, and then we return the element present at the index as the middle node of the linked list. The time and space complexity of this approach is , where is the number of nodes in the linked list. Let’s see if we can solve this problem with better time and space complexity.
Optimized approach using fast and slow pointers
We can use the fast and slow pointers to solve this problem with constant space complexity. The slow pointer traverses the linked list one step at a time, while the fast pointer takes two steps at a time. This makes the fast pointer reach the end of the linked list in iterations, and the slow pointer, by this time, reaches the middle of the linked list.
The following steps are applied when identifying the middle of the linked list:
-
Create two pointers,
slow
andfast
, initially at thehead
of the linked list, that is, pointing to the first node. -
Traverse the linked list using both pointers, where the
slow
pointer will move one step forward, and thefast
pointer will move two steps forward. -
When the
fast
pointer reaches the last element of the linked list, or becomes equal to NULL, theslow
pointer, at that time, will point to the middle node. Return the node that theslow
pointer points to.
The slides below help to understand the solution in a better way.
Level up your interview prep. Join Educative to access 70+ hands-on prep courses.