Finding the Middle Element of a Linked List using Java

In this blog post, we will learn how to write a Java program to find the middle element of a linked list.

When working with linked lists, one of the common tasks is to find the middle element. This task might sound simple with arrays, but since linked lists are sequential and don't provide direct access to their indices, we have to come up with efficient strategies to find the middle element. 

How the Algorithm Works

Two Pointers: Similar to detecting a cycle, we use two pointers – slow and fast. 

Movement: The slow pointer moves one step at a time, whereas the fast pointer moves two steps. 

Middle Element: By the time the fast pointer reaches the end of the list, the slow pointer will be in the middle of the list. 

Let's dive into the Java program that demonstrates this approach. 

Java Program to Find the Middle Element of a Linked List

class Node {
    int data;
    Node next;

    Node(int data) {
        this.data = data;
        this.next = null;
    }
}

public class MiddleElementFinder {

    public static int findMiddle(Node head) {
        if (head == null) {
            return -1;  // Return -1 or throw an exception based on use-case
        }

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;            // Move one step
            fast = fast.next.next;       // Move two steps
        }

        return slow.data;  // Middle element's data
    }

    public static void main(String[] args) {
        Node head = new Node(1);
        head.next = new Node(2);
        head.next.next = new Node(3);
        head.next.next.next = new Node(4);
        head.next.next.next.next = new Node(5);

        System.out.println("Middle Element: " + findMiddle(head));  // Should return 3

        head.next.next.next.next.next = new Node(6);
        System.out.println("Middle Element: " + findMiddle(head));  // Should return 4
    }
}

Output:

Middle Element: 3
Middle Element: 4

Explanation: 

Our basic building block is the Node class, representing elements of the linked list. 

The findMiddle method contains our two-pointer technique. While the fast pointer hasn't reached the end of the list, we move slow by one step and fast by two steps. 

When the loop ends, the slow pointer indicates the middle of the list. 

In the main method, we create a linked list and test our findMiddle function on it. First, we use a linked list of 5 nodes, which results in the middle node being 3. Then, we add another node, making the total count even. Now, the middle becomes 4, which is the second middle for even-sized lists. 

This approach is efficient, traversing the linked list only once, and can be a valuable technique to remember for both practical coding and interview scenarios.