Find the middle element of a Linked List in one pass

This is a very interesting question. We need to find the middle element of a Linked List and we don't know the length.

The best solution is to use the two-pointer technique: 

We have two pointers (fast and slow) and we move the fast two times, while we move the slow only one time.
This will cause the fast pointer to pass 2 times more elements than the slow pointer. This would mean, that when the fast comes to the end of the Linked List, the slow pointer will be exactly in the middle (pointing to the middle node of a list).

Solution

Note: Here, we are not using the LinkedList class from the java.util package, we are using our own LinkedList class that we built from scratch here -> Linked List data structure. It is a Singly-Linked List.

Here is the main method:

import java.util.Random;

public class Main {
    public static void main(String[] args) {
        LinkedList<Integer> linkedList = new LinkedList<>();
        addRandom(linkedList);
        System.out.println("Elements: ");
        linkedList.print();
        System.out.println();
        System.out.println("The middle element: " + linkedList.findMiddle());
    }

    public static void addRandom(LinkedList<Integer> linkedList) {
        Random random = new Random();
        // add 10 random elements
        for (int i = 0; i < 10; i++) {
            linkedList.add(random.nextInt(1000));
        }
    }
}

We have a method that adds random 10 numbers to our list so that we are able to find the middle element.

Now, let's add the method for finding the middle element to the LinkedList class:

public int findMiddle() {
    if (head == null) {
        throw new RuntimeException("List is empty");
    }

    Node<Integer> fast = (Node<Integer>) head;
    Node<Integer> slow = (Node<Integer>) head;

    while (fast != null && fast.next != null) {
        fast = fast.next.next;
        slow = slow.next;
    }

    return slow.data;
}

Here, we start by setting both fast and slow to the head node - since we need to start from the beginning of the list.

In the while loop, we are moving the fast pointer two places forward, and the slow pointer one place forward.

In the end, we end up having fast pointing to the last node and slow pointing to the middle node.
So we just return the data that slow is pointing to.

When we run the above program from the main method, we get the following output:

Elements: 

356 557 495 862 788 45 862 853 194 133 

The middle element: 788

The time complexity is O(n) since we are visiting each node - with the fast pointer.

The space complexity is O(1) since we are not creating any new data structure, hence no additional space in memory is required.