How to find middle node of LinkedList without using extra memory in java

To find the middle node of a LinkedList without using extra memory in Java, you can use the "tortoise and hare" algorithm. This algorithm uses 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 of the list, the slow pointer will be at the middle. Here's how you can implement it:

class Node {
    int data;
    Node next;

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

public class LinkedList {
    Node head;

    // Function to add a new node at the end
    public void add(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;
        }
    }

    // Function to find the middle node
    public Node findMiddle() {
        if (head == null) {
            return null;
        }

        Node slowPointer = head;
        Node fastPointer = head;

        while (fastPointer != null && fastPointer.next != null) {
            slowPointer = slowPointer.next;
            fastPointer = fastPointer.next.next;
        }

        return slowPointer;
    }

    // Function to print the LinkedList
    public void printList() {
        Node current = head;
        while (current != null) {
            System.out.print(current.data + " ");
            current = current.next;
        }
        System.out.println();
    }

    public static void main(String[] args) {
        LinkedList list = new LinkedList();
        list.add(1);
        list.add(2);
        list.add(3);
        list.add(4);
        list.add(5);

        list.printList();

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

Explanation:
Node Class: This is a simple class representing a node in the linked list.
LinkedList Class: This class contains methods to add a node, find the middle node, and print the linked list.
add Method: This method adds a new node to the end of the linked list.
findMiddle Method: This method uses the tortoise and hare algorithm to find the middle node. If the list is empty, it returns null.
printList Method: This method prints all the elements of the linked list.
main Method: This is the entry point of the program, where we create a linked list, add elements to it, print the list, and find and print the middle element.