Find the middle element of a linked list
Lists

Problem

Given a linked list, find the middle element.

Example:

Input: 10 -> 2 -> 3
Output: 2

Input: 10 -> 2 -> 3 -> 5
Output: 2
Analyze the problem

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;
}

Liked this article? Share it with others: