How to find middle node in a Singly Linked List in Java ?

In this post, We will learn How to find the middle node in a Singly Linked List in Java?

When We talk about finding the middle node of Linked List then we have the following two cases:

NOTE: Here our intension is to find a middle element of LinkedList in Single pass.

CASE 1: When Linked List has an even number of nodes

Case 2:When Linked List has an odd number of nodes

The logic used in the Source Code:

Here Idea is Very simple:

Step 1: We have to Take two references/pointers(slowReference & fastReference) , Initially both slowReference and fastReference are pointing to head of Linked List

Step 2: Traverse slowReference one Node and fastReference two Nodes in every iteration so that when fastReference reaches the end of the Linked List then slowReference will reach the middle of the list.

Below is the Complete Source code:

package com.kkjavatutorials.util;

/**
 * How to find middle node in a Singly Linked List in Java?
 * @author KK JavaTutorials
 */
public class LinkedList<T> {
	
	private Node<T> head;
	
	//This internal class represents Node in Linked List
	private static class Node<T>{
		
		private T data;
		private Node<T> next;
		public Node(T data) {
			super();
			this.data = data;
			this.next = null;
		}
	}
	
	/**
	 * This method insert Node in Linked List\
	 * @param data has to insert in the List
	 */
	public void insert(T data) {
		Node<T> newNode = new Node<T>(data);
		if(head == null) {
			head = newNode;
		}else {
			Node<T> currentNode = head;
			while (currentNode.next != null) {
				currentNode = currentNode.next;
			}
			 currentNode.next = newNode;
		}
	}
	
	/**
	 * Method to return Middle Node of Singly Linked List
	 * @return middle Node of Linked List
	 */
	public Node<T> getMiddleNodeOfLinkedList(){
		//Base Case If Linked List is Empty
		if(head == null) {
			return null;
		}
		
		//Initially both slowReference and fastReference pointing to head of Linked List
		Node<T> slowReference = head;
		Node<T> fastReference = head;
		
		/*Traverse slowReference one Node and fastReference two Nodes
		 * in every iteration so that when fastReference reaches end of the list
		 * then slowReference will reach middle of the list
		 */
		while(fastReference !=null && fastReference.next !=null) {
			slowReference = slowReference.next;
			fastReference = fastReference.next.next;
		}
		return slowReference;
	}
	
	/**
	 * Method which traverse Linked List and display all data.
	 */
	public void displayLinkedList() {
		Node<T> currentNode = head;
		while(currentNode!= null) {
			System.out.print(currentNode.data+"->");
			currentNode = currentNode.next;
		}
		System.out.println(currentNode);
	}
	
	public static void main(String[] args) {
		
		LinkedList<Integer> linkedList1 = new LinkedList<>();
		linkedList1.insert(10);
		linkedList1.insert(20);
		linkedList1.insert(30);
		linkedList1.insert(40);
		
		System.out.println("ListList 1::");
		linkedList1.displayLinkedList();
		Node<Integer> middleNodeOfLinkedList1 = linkedList1.getMiddleNodeOfLinkedList();
		System.out.println("Middle Element:"+middleNodeOfLinkedList1.data);
		
		System.out.println("-----------------------------------");
		LinkedList<Integer> linkedList2 = new LinkedList<>();
		linkedList2.insert(5);
		linkedList2.insert(10);
		linkedList2.insert(15);
		linkedList2.insert(20);
		linkedList2.insert(25);
		
		System.out.println("ListList 2::");
		linkedList2.displayLinkedList();
		Node<Integer> middleNodeOfLinkedList2 = linkedList2.getMiddleNodeOfLinkedList();
		System.out.println("Middle Element:"+middleNodeOfLinkedList2.data);
	}
}

100

101