Blog

Given a singly linked list and we have to find middle of the linked list.

For example, we have to find middle element from given linked list . If given linked list is 1->2->3->4->5 then output should be 3.

If there are even nodes, then there would be two middle nodes, we need to print second middle element. For example, if given linked list is 1->2->3->4->5->6 then output should be 4.

Example – Program to Find Middle Element of LinkedList

In this Java program, our class LinkedList which contains a collection of the node and has head and tail.

Each node contains data and addresses part. The main method of
LinkedListTest class is used to simulate the problem, where we created Linked List and added few elements on it and then iterate over them to find middle element of linked list in one pass in Java.

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

      LinkedList linkedList = new LinkedList();
      LinkedList.Node head = linkedList.head();
      linkedList.add( new LinkedList.Node("1"));
      linkedList.add( new LinkedList.Node("2"));
      linkedList.add( new LinkedList.Node("3"));
      linkedList.add( new LinkedList.Node("4"));
      linkedList.add( new LinkedList.Node("5"));
      
      //find middle element of LinkedList in single pass
      LinkedList.Node current = head;
      int length = 0;
      LinkedList.Node middle = head;
     
      while(current.next() != null){
          length++;
          if(length%2 ==0){
              middle = middle.next();
          }
          current = current.next();
      }
     
      if(length%2 == 1){
          middle = middle.next();
      }
 
     
      System.out.println(" Middle element of LinkedList : "+ middle);
       
    } 
   
}
 
class LinkedList{
    private Node head;
    private Node tail;
   
    public LinkedList(){
        this.head = new Node("head");
        tail = head;
    }
   
    public Node head(){
        return head;
    }
   
    public void add(Node node){
        tail.next = node;
        tail = node;
    }
   
    public static class Node{
        private Node next;
        private String data;
 
        public Node(String data){
            this.data = data;
        }
       
        public String data() {
            return data;
        }
 
        public void setData(String data) {
            this.data = data;
        }
 
        public Node next() {
            return next;
        }
 
        public void setNext(Node next) {
            this.next = next;
        }
       
        public String toString(){
            return this.data;
        }
    }
}
 

Output

Middle element of LinkedList : 3

Example – Another way

Traverse linked list using two pointers. Move one pointer by one and other pointer by two. When the fast pointer reaches end slow pointer will reach middle of the linked list.

class LinkedList {
  Node head;

  class Node {
    int data;

    Node next;

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

  void printMiddle() {
    Node slow_ptr = head;
    Node fast_ptr = head;
    if (head != null) {
      while (fast_ptr != null && fast_ptr.next != null) {
        fast_ptr = fast_ptr.next.next;
        slow_ptr = slow_ptr.next;
      }
      
      System.out.println("middle element of LinkedList : [" + slow_ptr.data + "] \n");
    }
  }

  public void push(int new_data) {
    /*
     * 1 & 2: Allocate the Node & Put in the data
     */
    Node new_node = new Node(new_data);

    /* 3. Make next of new Node as head */
    new_node.next = head;

    /* 4. Move the head to point to new Node */
    head = new_node;
  }

  public void printList() {
    Node tnode = head;
    while (tnode != null) {
      System.out.print(tnode.data + "->");
      tnode = tnode.next;
    }
    System.out.println("NULL"); 
  }

  public static void main(String[] args) {
    LinkedList list = new LinkedList();
    for (int i = 5; i > 0; --i) {
      list.push(i);
    }

    list.printList();
    list.printMiddle();
  }
}

Output

1->2->3->4->5->NULL
middle element of LinkedList : [3]