Java Program to Find the Middle Element of a Linked List

Introduction

Finding the middle element of a linked list is a common task that can be efficiently performed using the two-pointer technique. This method involves using two pointers: one pointer moves one step at a time while the other moves two steps. When the faster pointer reaches the end of the list, the slower pointer will be at the middle. This guide will walk you through writing a Java program that finds the middle element of a singly linked list.

Problem Statement

Create a Java program that:

Implements a singly linked list.
Finds and displays the middle element of the linked list.

Example:

Input: 1 -> 2 -> 3 -> 4 -> 5
Output: "The middle element is 3"
Input: 1 -> 2 -> 3 -> 4 -> 5 -> 6
Output: "The middle element is 4"

Solution Steps

Create the Linked List and Node Structure: Define a Node class to represent each element in the linked list and a LinkedList class to manage the list.
Add Nodes to the Linked List: Implement methods to add nodes to the linked list.
Find the Middle Element:

Implement the two-pointer technique to find the middle element.
The slow pointer moves one step at a time, while the fast pointer moves two steps.
When the fast pointer reaches the end, the slow pointer will be at the middle.

Display the Result: Output the middle element of the linked list.

Java Program

// Java Program to Find the Middle Element of a Linked List
// Author: https://www.rameshfadatare.com/

class Node {
    int data;
    Node next;

    // Constructor to initialize the node
    public Node(int data) {
        this.data = data;
        this.next = null;
    }
}

class LinkedList {
    Node head;

    // Method to add a new node at the end of the list
    public void add(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            // Step 1: Initialize the head if the list is empty
            head = newNode;
        } else {
            // Step 2: Traverse to the end of the list and add the new node
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to find the middle element of the linked list
    public Node findMiddle() {
        if (head == null) return null;

        // Step 3: Initialize two pointers, slow and fast
        Node slow = head;
        Node fast = head;

        // Step 4: Traverse the list with the two pointers
        while (fast != null && fast.next != null) {
            slow = slow.next;       // Move slow pointer by one step
            fast = fast.next.next;  // Move fast pointer by two steps
        }

        // Step 5: Return the slow pointer, which will be at the middle
        return slow;
    }

    // Method to display the linked list
    public void display() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " -> ");
            current = current.next;
        }
        System.out.println("null");
    }
}

public class FindMiddleElement {
    public static void main(String[] args) {
        LinkedList list = new LinkedList();

        // Adding elements to the linked list
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        System.out.println("Linked List:");
        list.display();

        // Finding the middle element
        Node middleNode = list.findMiddle();
        if (middleNode != null) {
            System.out.println("The middle element is: " + middleNode.data);
        } else {
            System.out.println("The linked list is empty.");
        }
    }
}

Explanation

Step 1: Initialize the Node Class

The Node class represents a single node in the linked list. Each node contains data and a reference to the next node in the list.
The constructor initializes the node with data and sets the next pointer to null.

Step 2: Initialize the LinkedList Class

The LinkedList class manages the linked list. The class contains the head node that points to the first node in the list.
The add() method appends a new node to the end of the list. If the list is empty, the head node is set to the new node.

Step 3: Initialize Two Pointers

The findMiddle() method initializes two pointers, slow and fast, both pointing to the head of the list.

Step 4: Traverse the List with Two Pointers

The slow pointer moves one step at a time, while the fast pointer moves two steps at a time.
This continues until the fast pointer reaches the end of the list or fast.next is null.

Step 5: Return the Slow Pointer

When the fast pointer reaches the end, the slow pointer will be at the middle of the list.
The method returns the node where the slow pointer is located.

Output Example

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> null
The middle element is: 3

Example with Even Number of Nodes

If you add one more element (6) to the list in the main method, the output will be:

Linked List:
1 -> 2 -> 3 -> 4 -> 5 -> 6 -> null
The middle element is: 4

Conclusion

This Java program demonstrates how to find the middle element of a singly linked list using the two-pointer technique. The program covers essential concepts such as linked list manipulation, node traversal, and efficient element retrieval. This exercise is valuable for understanding how to work with linked lists and implement efficient algorithms in Java programming.