In this tutorial, we will explore different approaches to find the middle node of a linked list in Java. This is a common coding interview question, and understanding its logic is essential for working with linked lists.

Approach 1: Using Slow and Fast Pointers (Tortoise and Hare Algorithm)

Logic

This is the most common and efficient method to find the middle node of a linked list. The approach uses two pointers:

• Slow Pointer: Moves one step at a time.
• 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.

Java Code

class Node {
    int data;
    Node next;

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

public class LinkedList {
    Node head;

    public Node findMiddle() {
        Node slow = head;
        Node fast = head;

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

        return slow;
    }

    public void insert(int data) {
        Node newNode = new Node(data);
        if (head == null) {
            head = newNode;
            return;
        }
        Node temp = head;
        while (temp.next != null) {
            temp = temp.next;
        }
        temp.next = newNode;
    }

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

        Node middleNode = list.findMiddle();
        System.out.println("Middle Node: " + middleNode.data);
    }
}

Output

Middle Node: 3

Time Complexity

O(n) – It traverses the list once.

Space Complexity

O(1) – It uses constant space for the two pointers.

Approach 2: Using Length of the Linked List

Logic

1. Traverse the linked list to count the number of nodes.
2. Traverse again to find the middle node using the formula:

middleIndex = length / 2

Java Code

public Node findMiddle() {
    int length = 0;
    Node temp = head;

    while (temp != null) {
        length++;
        temp = temp.next;
    }

    temp = head;
    for (int i = 0; i < length / 2; i++) {
        temp = temp.next;
    }

    return temp;
}

Time Complexity

O(n) – Two traversals are required.

Space Complexity

O(1) – No extra space is used.

Approach 3: Using Two Pointers from Both Ends (For Doubly Linked List)

If you are working with a doubly linked list (DLL), you can use two pointers:

• One starts from the head.
• One starts from the tail.
• Move both towards the center until they meet.

Java Code

public Node findMiddle(Node head, Node tail) {
    while (head != tail && head.next != tail) {
        head = head.next;
        tail = tail.previous;
    }
    return head;
}

Time Complexity

O(n/2) – But resolves to O(n).

Space Complexity

O(1).