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
