The linked list is one of the most important concepts and data structures to learn while preparing for interviews. Having a good grasp of Linked Lists can be a huge plus point in a coding interview.
In this problem, we are given a singly linked list. We have to find the middle of the linked list in a single traversal.
Problem Statement Understanding
Usually, whenever we find the middle of a linked list, 2 traversals are needed.
- 1st traversal to find the length of the list.
- 2nd traversal to reach the (length/2)th node of the list which is actually the middle node of the linked list.
But here we have to find the middle of the linked list in one traversal.
Suppose the given list is 5 → 10 → 15 → 4 → 8. The middle of the list will be 15.
Output : 15
Explanation: The middle of the given list is 15.
As stated in the problem statement, we have to find the middle of the list in a single traversal. How can we tackle this?
- What if we start by taking two pointers, say slow and fast, and make both of them point to the head initially.
- Now, what will happen if we make the slow jump one place and the fast jump two places (fast moving with twice the speed of slow).
- If we notice carefully, by doing the above step, when the fast will reach the end of the list, the slow will be pointing to the middle of the list.
- With the help of this technique, we can reach the middle node of a linked list in a single pass and hence our objective of finding the middle of linked list in one traversal will be achieved.
The reason why our slow pointer will be pointing to the middle of the linked list when our fast pointer is at end is that, as our slow pointer is travelling with half the speed of fast pointer so when the fast pointer will reach the end of the linked list, till that time slow pointer should have only travelled half the distance as travelled by fast pointer and hence it will be at the middle of the linked list.
Do you know what the above-explained method is called?
This above approach is called the slow and fast pointer method. The slow and fast pointer method has been explained in detail in the approach section and in the dry run.
Let us have a glance at the approach.
Let us see what the slow and fast pointer technique is:
Initially, both the slow and fast pointer will point to the head of the linked list. Then, we will move both of the pointers slow and fast until fast reaches the end. The fast pointer will jump two places, whereas the slow pointer will one place.
When the fast pointer will reach the end of the linked list, the slow pointer will be pointing to the middle of the linked list.
- Create two pointers slow and fast.
- Initially both slow and fast will be pointing to the head of the list.
- Now, make the slow pointer jump one place and the fast pointer jump two places until fast reaches the end of the list.
- When the fast pointer reaches the end of the list, the slow pointer will be pointing to the middle of the list.
- In the end, return the data of the slow pointer, as the slow will be pointing to the middle of the list.
class Node: def __init__(self, data): self.data = data self.next = None class LinkedList: def __init__(self): self.head = None def push(self, new_data): new_node = Node(new_data) new_node.next = self.head self.head = new_node def printMiddle(self): slow_ptr = self.head fast_ptr = self.head if self.head is not None: while (fast_ptr is not None and fast_ptr.next is not None): fast_ptr = fast_ptr.next.next slow_ptr = slow_ptr.next print("The middle element is: ", slow_ptr.data) list1 = LinkedList() list1.push(8) list1.push(4) list1.push(15) list1.push(10) list1.push(5) list1.printMiddle()
The middle element is: 15
Time Complexity: O(n), as list traversal is needed.
So, in this article, we have tried to explain the most efficient approach to find the middle of a linked list in a single traversal. This is an important concept when it comes to coding interviews. If you want to solve more questions on Linked List, which are curated by our expert mentors at PrepBytes, you can follow this link Linked List.