Find the Middle Element in Linked List
FREE
Problem Statement
You are given the head of a linked list, write a program to Find middle element in linked list. When there are even number of nodes in linked list, then there would be two middle nodes, return the second middle node.
Example
Input-1
Output-1
Explanation
Here, 3 is the middle node of the linked list as shown below.
Input-2
Output-2
Explanation
Here, there are even number of nodes in linked list, So there would be two middle nodes 3 and 4, we will return the second middle node i.e 4 as shown below.
Constraints
Algorithm 1 - Brute-Force approach - Using Extra Memory
Intuition:
The naive approach is to use the extra space as an array, store all the linked list node into the array maintaining the same order. After adding all the nodes into an array the size becomes equal to the length of the linked list, Now simply return the middle element of the array by using index count/2.
Algorithm
- Create a list of types ListNode temp to store all the nodes.
- Initialize a count variable to count the number of nodes.
- Traverse through the linked list using a while loop.
- Also, keep inserting the node values to the extra array from the linked list until we reach the NULL pointer.
- Now return the count/2 ^th^ index element from the list of ListNode.
Code Implementation
Code in C++
Code in Java
Code in Python
Output
Time Complexity
The time complexity is O(n). Since we are traversing the linked list only once to find middle element of linked list.
Space Complexity
The space complexity is O(n). Since extra space is used in the Program to Find middle element in linked list for storing all the nodes in a list of size n.
Algorithm 2 - By Counting Nodes - Double traversal
Intuition:
One intuition is to traverse through the Linked List while maintaining a count of nodes. After counting n total number of nodes, traverse the linked list once again but only up to the n/2^th^ node and return this node. It is better than previous approach as this algorithm does not use extra memory.
Algorithm
- Initialize a count variable to count the number of nodes.
- Traverse through all the linked list nodes using a while loop and count the total number of nodes.
- Initialize a ListNode middle to count the number of nodes.
- Now traverse through the linked list once again using a while loop which runs until i < n/2 and iterates over the linked list.
- At the end of the loop, return the middle node.
Code Implementation
Code in C++
Code in Java
Code in Python
Output
Time Complexity
The time complexity is O(n). Since we are traversing the linked list two times to find middle element of linked list.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find middle element in linked list.
Algorithm 3 - Efficient Approach - Using Slow and Fast Pointers
Intuition:
The efficient approach is to traverse through the linked list using two-pointers i.e slow pointer and fast pointer. Increment slow_ptr by 1 step and fast_ptr by 2 steps, As a result, the fast pointer will travel double than that of the slow pointer. So When the fast pointer will reach to the end of the linked list, slow point would still be at the middle of the linked list. Think!
This approach is efficient and better than the previous approaches because only single traversal is needed in this algorithm without using extra memory.
Algorithm
- Initialize two pointers slow_ptr and fast_ptr and point both of them to the head node.
- Until fast_ptr is NULL or the next of fast_ptr is NULL, move slow_ptr by one step and fast_ptr by two steps at the same time.
- As we can see slow_ptr is pointing towards the middle of the Linked List. Hence return the slow_ptr.
Code Implementation
Code in C++
Code in Java
Code in Python
Output
Time Complexity
The time complexity is O(n). Since we are traversing the linked list once to find middle element of linked list.
Space Complexity
The space complexity is O(1). Since no extra space is used in the Program to Find middle element in linked list.
Conclusion
- We have given the head of a singly linked list, we had to write a program to Find middle element in linked list.
- If there were even number of nodes in linked list, then there would have two middle nodes, we had to return the second middle node.
- For eg, A linked list is given 1->2->3->4->5, here the middle of list is 3.
- The naive approach takes O(n) time complexity as two traversals were needed, and O(n) space complexity because an array was used as an extra space.
- On the other hand, the most efficient approach to Find middle element in linked list Using Slow and Fast Pointers takes O(n) time complexity and O(1) as space complexity.
- if we increment a slow_ptr by 1 step and fast_ptr by 2 steps and when the fast pointer will reach at the end, the slow pointer will be at the middle of linked list.
FAQ
Q. Will the above approaches work if the linked link has a loop?
A. No, if the linked list has a loop, the traversal will not be possible and the pointer will be stuck in a cyclic loop forever. Hence gives a Time Limit Exceed error.
Q. How do we modify the above code to delete the middle node?
A. Instead of returning the middle of the linked list just update the middle node's value with the value of its next node, and finally point the next node of the middle node to the next of next node.
Q. Can we solve the above problem with some different approach?
A. Yes, Initialize the middle pointer as head and traverse through the list from the head, When the counter is odd while traversing, increase the counter and change mid to mid->next. So the middle pointer will travel only half of the size of the list.
Q. What are some similar coding questions of Linked List.
A. Refer Detect Loop in Linked List Refer Remove Nth Node from List End Refer Reverse a Linked List