Java Program to Get the middle element of LinkedList in a single iteration

In this example, we will learn to get the middle element of the linked list in a single iteration in Java.

Example 1: Get the middle element of LinkedList in a single search

class LinkedList {

  // create an object of Node class
  // represent the head of the linked list
  Node head;

  // static inner class
  static class Node {
    int value;

    // connect each node to next node
    Node next;

    Node(int d) {
      value = d;
      next = null;
    }
  }

  public static void main(String[] args) {

    // create an object of LinkedList
    LinkedList linkedList = new LinkedList();

    // assign values to each linked list node
    linkedList.head = new Node(1);
    Node second = new Node(2);
    Node third = new Node(3);

    // connect each node of linked list to next node
    linkedList.head.next = second;
    second.next = third;

    // print the linked list
    Node pointer = linkedList.head;
    System.out.print("LinkedList: " );
    while (pointer != null) {
      System.out.print(pointer.value + " ");
      pointer = pointer.next;
    }

    // Find the middle element
    Node ptr1 = linkedList.head;
    Node ptr2 = linkedList.head;

    while (ptr1.next != null) {

      // increase the ptr1 by 2 and ptr2 by 1
      // if ptr1 points to last element
      // ptr2 will points to middle element
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
      }
    }

    System.out.println("\nMiddle Element: " + ptr2.value);

  }
}

Output

LinkedList: 1 2 3 
Middle Element: 2

In the above example, we have implemented the linked list data structure in Java. We then find the middle element of the linked list in a single loop. Notice the code,

    while (ptr1.next != null) {

      // increase the ptr1 by 2 and ptr2 by 1
      // if ptr1 points to last element
      // ptr2 will points to middle element
      ptr1 = ptr1.next;
      if(ptr1.next !=null) {
        ptr1 = ptr1.next;
        ptr2 = ptr2.next;
      }
    }

Here, we have two variables ptr1 and ptr2. We use these variables to iterate through the linked list.

In each iteration, the ptr1 will access the two nodes and the ptr2 will access the single node of the linked list.

Now, when the ptr1 reaches the end of the linked list, the ptr2 will be in the middle. In this way, we are able to get the middle of linked list in a single iteration.

Example 2: Get the middle element of LinkedList using the LinkedList class

import java.util.LinkedList;

class Main {
  public static void main(String[] args){

    // create a linked list using the LinkedList class
    LinkedList<String> animals = new LinkedList<>();

    // Add elements to LinkedList
    animals.add("Dog");
    animals.addFirst("Cat");
    animals.addLast("Horse");
    System.out.println("LinkedList: " + animals);

    // access middle element
    String middle = animals.get(animals.size()/2);
    System.out.println("Middle Element: " + middle);
    }
}

Output

LinkedList: [Cat, Dog, Horse]
Middle Element: Dog

In the above example, we have used the LinkedList class to implement the linked list data structure. Notice the expression,

animals.get(animals.size()/2)

size()/2 – returns the position of middle element
get() – returns the element at the middle position

Share on Facebook