Problem
Given a linked list, find the middle element.
Example:
Input: 10 -> 2 -> 3
Output: 2
Input: 10 -> 2 -> 3 -> 5
Output: 2
Approach
The first solution that comes to mind is to iterate over the list and count the number of elements. We can then do another pass at the list stopping at the element in the N/2 position. This however requires 2 passes at the list and we can certainly do better. Perhaps using 2 pointers that travel at different speed?
Solution
This classic problem can be efficiently solved with a single pass of the list. We can use 2 pointers that travel at slow speed (1 node at a time) and at fast speed (2 nodes at a time). This means that when the faster pointer is at the end of the list the slower pointer will be exactly in the middle pointing at the node we want to return.
ListNode findMiddleElement(ListNode head) {
if(head == null) {
return head;
}
ListNode slow = head;
ListNode fast = head.next;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}