Java program to find middle of a linked list

Java program to find middle of a linked list

In here we are learning about a Java program to find the middle of a linked list. To find a middle of a linked , before that we should know that the number of link nodes are even or odd . If it’s odd then we have to take two pointer’s p1 and p2 as shown in the diagram p1 will move forward by one node and p2 will move forward two nodes. When p2 reaches the end of a linked list at that time p1 will be at the middle node of the linked list.

Java program to find the middle of a linked list, (even case) When given number of link nodes are even we will follow the same fashion ad we are doing in odd case but over here we will divide the number of link nodes by 2 so as to get the middle node of a linked list

Example:

input: 1–>2–>3–>4–>5

output

3

The middle of a given linked list is 3

Java program to find middle of a linked list

Algorithm.

Step 1- Start

Step 2- Initialize a class

Step 3- Give input

Step 4- Node constructor

Step 5- Linked list constructor

Step 6- Add a function to find the size of a linked list. // return this.size

Step 7- Check whether the linked list is empty or not // return this.size () == 0

Step 8- run a loop for traversing the pointer and then print the linked list

Step 9- Add a node in the beginning.

Step 10- Create a temp node which points towards the head

Step 11- Linked list is empty, then head and tail both is temp

Step 12- add a function for finding the mid node.

Step 13- Take two pointers p1 and p2

Step 14- Move p1 by one node and p2 by two nodes

Step 15- When p2 reaches the end of a linked list, p1 will point to the middle node.

Step 16- End.

Java program to find middle of a linked list

Java Program

import java.util.*;

public class PrepInsta
{

  public static void main (String[]args) throws Exception
  {
    LinkedList ll = new LinkedList ();
      ll.addFirst (30);
      ll.addFirst (18);
      ll.addFirst (13);
      ll.addFirst (9);
      ll.addFirst (7);

      ll.display ();

      System.out.println (ll.mid ());

  }

}

class Middle_LinkedList
{
  private class Node
  {
    int data;
    Node next;

// Node constructor
// There are two fields in the node- data and address of next node
    public Node (int data, Node next)
    {
      this.data = data;
      this.next = next;
    }
  }

  private Node head;
  private Node tail;
  private int size;

// Linked list constructor
  public LinkedList ()
  {
    this.head = null;
    this.tail = null;
    this.size = 0;

  }

// Function to find the size of linked list
  public int size ()
  {
    return this.size;
  }

// Function to check whether linked list is empty or not
  public boolean isEmpty ()
  {
    return this.size () == 0;
  }

// Function to traverse and print the linked list
  public void display ()
  {
    Node temp = head;
    while (temp != null)
      {
	System.out.print (temp.data + "  ");

	temp = temp.next;
      }
    System.out.println ("END");
  }

// Function to add a node in beginning of linked list
  public void addFirst (int item)
  {
// Create a temp node which points to head
    Node temp = new Node (item, head);

// If linked list is empty, temp is the head and tail node both
    if (this.size == 0)
      {
	this.head = this.tail = temp;
      }

// else set the head such that it now points to temp node
    else
      {
	this.head = temp;

      }

    this.size++;
  }

  public int mid ()
  {
    return this.midNode ().data;
  }

//Function to find the mid node
  private Node midNode ()
  {

//Take two pointers p1 and p2
    Node p1 = this.head;
    Node p2 = this.head;

//Move p1 by one node and p2 by two nodes
    while (p2.next != null && p2.next.next != null)
      {
	p1 = p1.next;
	p2 = p2.next.next;
      }

//When p2 reaches the end, p1 will point to the mid node
    return p1;

  }
}
Output
Given linked list
7-->9-->13-->18-->30
Middle of a linked list
13