Finding the Middle Element of a Linked List using Java

Introduction

Finding the middle element of a linked list is a common problem in data structures. In a singly linked list, each node points to the next node, and finding the middle element typically involves traversing the list. A common approach is to use two pointers: a slow pointer and a fast pointer. The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end, the slow pointer will be at the middle.

Problem Statement

Create a Java program that:

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

Example 1:

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

Example 2:

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

Solution Steps

1. Define the Node Class: Create a class to represent a node in the linked list, containing data and a reference to the next node.
2. Define the LinkedList Class: Create a class to manage the linked list, including methods to insert elements and find the middle element using two pointers.
3. Find the Middle Element: Implement a method to find the middle element by moving the slow and fast pointers through the list.
4. Display the Middle Element: Print the middle element of the linked list.

Java Program

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

class LinkedList {
    Node head;

    // Method to insert a new node at the end of the list
    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
        } else {
            Node current = head;
            while (current.next != null) {
                current = current.next;
            }
            current.next = newNode;
        }
    }

    // Method to find the middle element of the linked list
    public int findMiddle() {
        if (head == null) {
            throw new IllegalStateException("List is empty");
        }

        Node slow = head;
        Node fast = head;

        while (fast != null && fast.next != null) {
            slow = slow.next;        // Move slow pointer by 1
            fast = fast.next.next;   // Move fast pointer by 2
        }

        return slow.data; // Slow pointer is now at the middle
    }

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

        // Insert elements into the linked list
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.insert(4);
        list.insert(5);

        // Find and display the middle element
        int middleElement = list.findMiddle();
        System.out.println("The middle element is " + middleElement);

        // Insert more elements and find the middle again
        list.insert(6);
        middleElement = list.findMiddle();
        System.out.println("The middle element is " + middleElement);
    }
}

Explanation

• Node Class: This class defines a node in the linked list, with an integer data and a next pointer to the next node in the list.

• LinkedList Class: This class manages the linked list and provides methods to insert nodes and find the middle element using the two-pointer technique.

  • insert(int data): Adds a new node with the given data at the end of the list.

  • findMiddle(): Finds the middle element by using two pointers (slow and fast). The slow pointer moves one step at a time, while the fast pointer moves two steps at a time. When the fast pointer reaches the end of the list, the slow pointer is at the middle.

• Main Method: The main method demonstrates the functionality by creating a linked list, inserting elements, finding the middle element, and displaying it.

Output Example

Example 1:

The middle element is 3
The middle element is 4

In this example:

• Initially, the linked list is 1 -> 2 -> 3 -> 4 -> 5. The middle element is 3.
• After adding another element, the linked list becomes 1 -> 2 -> 3 -> 4 -> 5 -> 6. The middle element is now 4.

Conclusion

This Java program effectively finds the middle element of a singly linked list using the two-pointer technique (slow and fast pointers). By moving the fast pointer at twice the speed of the slow pointer, the program can efficiently determine the middle element of the list. This method is commonly used in various applications involving linked lists, such as in data structures and algorithms.