Find the middle of a given linked list data structure

Question: In given a Linked List,  find the middle of the list and print the number.

Input : -> 4-> 2-> 7-> 9-> 1

Output : 7

Before starting you have to must know about Linked list and how to create it and Inserting node (data) in LinkedList.

There is many approach to find middle number in LinkedList.

1.  Single pointer approach

In this approach, we will scan the entire list and count the number of nodes. We divide the number by 2 and then again traverse the list up to that node.

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            int middleNode = (count() % 2 == 0) ? (count() / 2) : ((count() + 1) / 2);

            Node pointerNode = head;
            int countNodes = 0;
            while (countNodes != middleNode -1) {
                pointerNode = pointerNode.next;
                countNodes ++;
            }
            System.out.println("\nMiddle node of linked List is " + middleNode);
            System.out.println("Middle node data is " + pointerNode.data);
        }
    }
    //Returns count of nodes in linked list (iteration)
    public int count() {
        int a = 0;
        Node n = head;
        while (n != null) {
            n = n.next;
            a++;
        }
        return a;
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findMiddleNode();
    }
}

Output : -> 4-> 2-> 7-> 9-> 1
Middle node of linked List is 3
Middle node data is 7

Time Complexity: Time for finding the length of list + Time for locating middle node = O(n) + O(n) ≈ O(n)
Space Complexity: O(1)

2. Using 2 pointers

With 2 pointers to traverse the list ,we can find the middle of list with only one scan on the Linked List.

  • pointer1 travels one node at a time
  • pointe2 travels two nodes a time.

Thus, when pointe2 reaches the end of the Linked List, pointer1 will point at the middle of the Linked List.

package in.eyehunt.data.struc;
public class LinkedList {
    Node head; // head of list
    // Linked list Node.
    class Node {
        int data;
        Node next;
        // Parameterized constructor
        Node(int d) {
            data = d;
            next = null;
        }
    }
    void push(int n) {
        //create new node
        Node newNode = new Node(n);
        // next node is head
        newNode.next = head;
        // move had point to new node
        head = newNode;
    }
    void findMiddleNode() {
        if (head == null) {
            System.out.println("LinkedList is null");
        } else {
            Node pointer1 = head;
            Node pointer2 = head;

            while (pointer2 != null && pointer2.next != null) {
                pointer1 = pointer1.next;
                pointer2 = pointer2.next.next;
            }
            System.out.println("\nMiddle node data is " + pointer1.data);
        }
    }
    void printAllNodes() {
        Node node = head;
        while (node != null) {
            System.out.print("-> " + node.data);
            node = node.next;
        }
    }
    public static void main(String a[]) {
        //create a simple linked list with 4 nodes
        LinkedList linkedList = new LinkedList();
        linkedList.push(1);
        linkedList.push(9);
        linkedList.push(7);
        linkedList.push(2);
        linkedList.push(4);
        linkedList.printAllNodes();
        linkedList.findMiddleNode();
    }
}

Output: -> 4-> 2-> 7-> 9-> 1
Middle node data is 7

Time Complexity: O(n)
Space Complexity: O(1)

here is more LinkedList interview questions :

  1. Program for find n’th node from the end of a Linked List
  2. Reverse a Linked list data structure in java
  3. Inserting a new node in a linked list data structure
  4. Find Length of a Linked List data structure (Iterative and Recursive)

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.