Algorithm

1. Set slow and fast pointers to the head of the LinkedList.
2. Loop until fast reaches the end of the list or fast.next is null:
    a. Move slow one step.
    b. Move fast two steps.
3. The slow pointer is now at the middle element of the LinkedList.

Code Examples

#1 Code Example- Get the middle element of LinkedList in a single search

Code - Java Programming

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

  }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
LinkedList: 1 2 3
Middle Element: 2

#2 Code Example- Get the middle element of LinkedList using the LinkedList class

Code - Java Programming

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);
    }
}
Copy The Code & Try With Live Editor

Output

x
–
+
cmd
LinkedList: [Cat, Dog, Horse]
Middle Element: Dog
Advertisements

Demonstration

Java Programing Example to Get the middle element of LinkedList in a single iteration-DevsEnv