In this article we will see How to find Middle node of a LinkedList, in case the list contains odd number of node than to find first node i.e. {1,2,3,4} - Middle 2, {1,2,3,4,5} - Middle 3.

Input: {1,2,3,4}, Output: 2
Input: {1,2,3,4,5}, Output: 3

A simple solution is to traverse a list to find middle total number of nodes, iterate again upto totalNodes /2 to find middle element of the list.

An optimised solution is to traverse a list only once to find the middle, the idea is to have two variables increment first variable by one and other by 2 until the second one reach to the end of list, the first variable at this moment will be the middle.

package com.tb.array;

public class MyLinkedList {

 Node head;

 static class Node {
  Node next;
  T data;

  public Node(T data) {
   super();
   this.data = data;
  }
 }

 /* Add an element at the end of list */
 public void add(T t) {
  if (head == null) {
   head = new Node(t);
   return;
  }

  Node current = head;
  while (current.next != null)
   current = current.next;
  current.next = new Node(t);
 }

 // Traverse over linked list
 public void iterate() {
  Node current = head;
  while (current != null) {
   System.out.print(current.data + ", ");
   current = current.next;
  }
  System.out.println();
 }

 // Return middle node of a list
 public Node middle() {
  if (head == null)
   return null;
  Node slow = head, fast = head;

  while (fast.next != null && fast.next.next != null) {

   slow = slow.next;
   fast = fast.next.next;
  }
  return slow;

 }

 public static void main(String[] args) {
  MyLinkedList myList = new MyLinkedList();

  // add elements at the end
  myList.add(1);
  myList.add(2);
  myList.add(3);
  myList.add(4);
  myList.iterate();

  System.out.println("Middle: " + myList.middle().data);

  myList.add(5);
  myList.iterate();

  System.out.println("Middle: " + myList.middle().data);

 }
}

Output: Above code will print something like this on console.

1, 2, 3, 4, 
Middle: 2
1, 2, 3, 4, 5, 
Middle: 3

This program implements how to find middle node of a LinkedList in O(log n) time complexity and O(1) extra space, if you have some better way to solve this logical problem please share your thoughts in comments below.