Finding middle node of a linked list in Java

To find the middle node of a linked list we have various methods in Java.

Method 1

In this method two pointers are used, one of which advances quickly, and the other of which goes slowly. The fast pointer reaches the end of the list before the two-pointers do. Once the fast pointer has reached the end of the linked list, we check the location of the slow pointer, which moves one step at a time. the slow pointer is now at the middle node of the linked list.

Program for Finding middle node of a linked list using two pointer technique

MiddleNodeTwoPointer.java

// importing required packages
import java . util . * ;
import java . io . * ;
class Node 
{  
int n1 ;  
Node next;  
Node ( int n )  
{  
this . n1 = n ;    
this . next = null ;  
}  
}  
public class MiddleNodeTwoPointer  
{  
// find static method used to locate the middle element
public void find ( Node n )  
{  
if ( n == null )   
{   
return  ;  
}  
// declaring two pointers 
// one pointer is named slow pointer
Node slow_P  = n ;    
// Other pointer is named fast pointer
Node fast_p = n ;  
while  ( fast_p ! = null && fast_p . next != null )  
{   
fast_p  = fast_p . next . next ;  
slow_P  = slow_P . next ;  
}  
System . out . println ( " The middle node in  the linked list is: " + slow_P . n1 ) ;  
}  
// Main  method where execution of the program started 
public static void main ( String argvs [ ] )  
{  
// declaring head node of the linked list  
Node head = new Node ( 12 ) ;  
// adding nodes to the linked list 
Scanner sc = new Scanner ( System . in ) ;
System . out . println ( " Enter the element to be inserted " ) ;
int n = sc . nextInt ( ) ;
head . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next = new Node ( n ) ;   
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next . next . next = new Node ( n )  ;  
System . out . println ( " Enter the element to be inserted " ) ;
n = sc .nextInt ( ) ;
head . next . next . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " )    ;
n = sc . nextInt ( ) ;
head . next . next . next . next . next . next = new Node ( n ) ;  
MiddleNodeTwoPointer o1 = new MiddleNodeTwoPointer  ( ) ;  
o 1. find  ( head ) ;  
}  
}  

Output

Method 2

In this method, we will start by determining the linked list's overall size. All of the connected list's nodes will now be pushed into the stack. The entire size is then divided by two, and we repeat the pop operation on the stack up to that number of times. Top   node present in the stack represents middle node.

Program for Finding middle node of a linked list using stacks

MiddleNode2.java

import java . util . * ;  
class Node  
{  
int n1;  
Node next ;  
Node ( int n)  
{   
this . n1 = n ;    
this . next  = null ;  
}  
}  
public class MiddleNode
{  
public int size ( Node h )  
{  
int size1 = 0;  
while ( h ! = null )  
{  
size1 = size1 + 1 ;  
h = h . next ;  
}  
return size1 ;  
}  
public void findNode ( Node n )  
{  
Stack < Node > stk = new Stack < Node > ( ) ;  
Node head = n ;   
while  ( head ! = null )  
{  
stk . push ( head ) ;  
head = head . next ;  
}  
int s = size ( n ) ;  
s = s / 2 ;  
while ( s ! = 0 )  
{  
stk . pop ( ) ;  
s = s - 1;  
}  
int val  = ( stk . peek ( ) ) . n1 ;  
System . out . println ( " The middle node of the linked list is : " + val ) ;  
}  
// main method where execution of the program starts  
public static void main ( String argvs [ ] )  
{  
// declaring head node of the linked list  
Node head = new Node ( 12 ) ;  
// adding nodes to the linked list 
Scanner sc = new Scanner ( System . in ) ;
System . out . println ( " Enter the element to be inserted " ) ;
int n = sc . nextInt ( ) ;
head . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next = new Node ( n) ;   
System . out.println (" Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next . next . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n=sc . nextInt ( )  ;
head . next . next . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( )  ; 
head . next . next . next . next . next . next = new Node ( n ) ;
// creating an object of the class StackExample1  
MiddleNode  O1 = new MiddleNode  ( ) ;  
// invoking the method findNode ( )  
O1 . findNode ( head ) ;  
}  
}  

Output

Method 3

In this method, the middle node of the linked list will be located using a queue. We will start by determining the linked list's overall size. All of the connected list's nodes will now be pushed into the queue. The total size is then divided by 2, and whatever number results, we remove nodes from the queue up to that many times. Our response, the middle node, is the queue's top or peek node.

Program for Finding middle node of a linked list using Queues

// importing required packages
import java . util .*;  
// creating class for nodes
class Node  
{  
// value at node
int n1; 
// address of the next node
Node next ;  
// constructor for the class node 
Node ( int n )  
{  
this . n1 = n ;  
this. next = null ;  
}  
}  
public class QueueMiddle  
{  
public int size ( Node head )  
{    
int size1 = 0 ;   
while ( head ! = null )  
{  
size1 = size1 + 1 ;      
head = head . next  . ;  
}  
return size1 ;  
}  
public void find ( Node n )  
{  
Queue < Node > q = new LinkedList < Node > ( ) ;  
Node h =  n ;  
// pushing the node from the stack  
while ( h  ! = null )  
{  
q . add ( h ) ;  
h = h . next ;  
}  
// calling the method size ( )  to   find the size of the linked list  
int s = size(n);  
// dividing the size by 2  to find middle point
s = s / 2 ;  
while ( s ! = 0 )   
{  
q . remove ( ) ;  
s = s – 1 ;  
}  
// the value of the top node present in the stack   
int val = ( q . peek ( ) ) . n1 ;  
System . out . println ( " The middle node in  the given  linked list is : " + val ) ;  
}  
// main method  where execution of the program starts
public static void main ( String argvs [ ] )  
{  
// head node
Node head = new Node ( 43 ) ;  
Scanner sc = new Scanner ( System . in ) ;
System . out . println ( " Enter the element to be inserted " ) ;
int n = sc . nextInt ( ) ;
head . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n=sc . nextInt ( ) ;
head . next . next = new Node ( n ) ;  
System . out .  println ( " Enter the element to be inserted " ) ; 
n=sc . nextInt ( ) ;
head . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " ) ;
n=sc . nextInt ( ) ;
head . next . next . next . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n = sc . nextInt ( ) ;
head . next . next . next . next . next = new Node ( n ) ;
System . out . println ( " Enter the element to be inserted " ) ;
n=sc . nextInt ( ) ;
head . next . next . next . next . next . next = new Node ( n ) ;
QueueMiddle o1 = new QueueMiddle (  )  ;  
// calling  method find ( )  
o1 . find ( head ) ;  
}  
}  

Output

Method 4

To locate the middle node of the linked list using this method, we will only utilise one pointer. We will start by determining the linked list's overall size. Next, we divide the total size by 2, and whichever number results, we shift the pointer to that many times, beginning at the head node. The middle node of the linked list is the node to which the pointer is now pointing.

Program for Finding middle node of a linked list using one pointer

import java.util.*;
class Node  
{  
int n1;  
Node next;  
Node(int n)  
{  
this.n1 = n;  
this.next = null;  
}  
}  
public class Main  
{  
public int size(Node head)  
{  
int size1 = 0;  
while(head != null)  
{  
size1 = size1 + 1;  
head = head.next;  
}  
return size1;  
}  
 public void findNode(Node n)  
{  
Node head = n;  
int s = size(n);  
s = s / 2;  
 while(s != 0)  
{  
  head = head.next;  
s = s - 1;  
}  
int val = head.n1;  
System.out.println("The middle node in the linked list is: " + val);  
 }  
public static void main(String argvs[])  
{  
Scanner sc=new Scanner(System.in);
// head node
Node head = new Node ( 43 ) ;  
// Scanner sc = new Scanner ( System . in ) ;
System . out . println ( " Enter the element to be inserted " ) ;
int n = sc . nextInt ( ) ;
head . next = new Node ( n ) ;  
System . out . println ( " Enter the element to be inserted " ) ;
n=sc . nextInt ( ) ;
head . next . next = new Node ( n ) ;  
System . out .  println ( " Enter the element to be inserted " ) ; 
n=sc . nextInt ( ) ;
head . next . next . next = new Node ( n ) ;
Main o1 = new Main();    
// invoking the method findNode()  
o1.findNode(head);  
}  
}  

Output