How to Find Middle Element of Linked List in Java in Single Pass

How do you find the middle element of LinkedList in one pass is a programming question often asked Java and non-Java programmers in telephonic Interview. This question is similar to checking palindrome or calculating the factorial, where the Interviewer sometimes also asks to write code. In order to answer this question candidate must be familiar with the LinkedList data structure i.e. In the case of the singly LinkedList, each node of Linked List contains data and pointer, which is the address of the next Linked List and the last element of Singly Linked List points towards the null. Since in order to find the middle element of the Linked List you need to find the length of the linked list, which is counting elements till the end i.e. until you find the last element of the Linked List.

What makes this data structure Interview question interesting is that you need to find the middle element of LinkedList in one pass and you don’t know the length of LinkedList.

This is where candidates’ logical ability puts into the test,  whether he is familiar with space and time trade-off or not etc.

As if you think carefully you can solve this problem by using two pointers as mentioned in my last post on How to find the length of the Singly Linked List in Java.

By using two pointers, incrementing one at each iteration and other at every second iteration. When the first pointer will point at end of Linked List, the second pointer will be pointing at a middle node of the Linked List.  

In fact, this two pointer approach can solve multiple similar problems like how to find the third node from last in a Linked List in one Iteration or how to find an Nth element from last in a Linked List. In this Java programming tutorial, we will see a Java program that finds the middle element of Linked List in one Iteration.
Btw, if you are new to Algorithms and Data Structure and not familiar with an essential data structure like a linked list, array or binary tree then  I suggest you go through a good, comprehensive online course like Data Structures and Algorithms: Deep Dive Using Java to learn the basics and brush up the fundamentals.

How to Find Middle Element of LinkedList in One Pass

Here is a complete Java program to find the middle node of Linked List in Java. Remember LinkedList class here is our custom class and don’t confuse this class with java.util.LinkedList is a popular Collection class in Java.

In this Java program, our class LinkedList represents a linked list data structure that contains a collection of the node and has a 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 the middle element of linked list in one pass in Java.

If you want to learn more about linked list data structure and different types of linked lists like a singly linked list, doubly linked list, circularly linked list et all then you can also check the Algorithms and Data Structures – Part 1 and 2 courses on Pluralsight. One of the better course to learn data structure and algorithms.

Btw, you would need a Pluralsight membership to access this course. If you are not a member, you can still access this course by using the 10-day free pass provided by Pluralsight to explorer its portal and online courses.

Java Program to Find the Middle Node of a Linked list in a Single-pass

import test.LinkedList.Node;

/**
 * Java program to find middle element of linked list in one pass.
 * In order to find middle element of a linked list
 * we need to find the length first but since we can only
 * traverse linked list one time, we will have to use two pointers
 * one which we will increment on each iteration while 
 * other which will be incremented every second iteration.
 * So when the first pointer will point to the end of a
 * linked list, second will be pointing to the middle
 * element of a linked list
 *
 * @author Javin Paul
 */
public class LinkedListTest {
 
 
    public static void main(String args[]) {
        //creating LinkedList with 5 elements including head
      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"));
   
      //finding 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("length of LinkedList: " + length);
      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:
length of LinkedList: 4
the middle element of LinkedList: 2

That’s all on How to find the middle element of LinkedList in one pass. As I said this is a good interview question to separate programmers from non-programmers. Also, the technique mentioned here to find the middle node of LinkedList can be used to find the 3rd element from Last or nth element from last in a LinkedList as well.