How to Print the middle node of a linked list using java
By Anubhav SrivastavaHi, coders! Most of you people are familiar with the linked list data structure but did you people ever tried to print the middle node of a singly linked list in Java, if not I am here with a good approach for the same. We know that we are always provided with the head node of a linked list to access it. So if you have to print the middle node of a linked list, there are various approaches like:
First, traverse the linked list and count the number of nodes and then again traverse the linked list up to half of the total number of nodes.
This is a very simple approach but there is a concept of a fast and a slow pointer through which the middle node of a linked list can be accessed. This approach is also helpful in various problems related to linked list which you people will come to know when you will be solving more linked list questions.
Method to implement the fast and slow pointer approach
- Declare two variables that are of type node of a linked list.
- Initially, both will be pointing to the head node of the linked list.
- While traversing the linked list, the fast pointer will move by two nodes and the slow pointer will move by one node.
- When the fast pointer will reach the end of the linked list slow pointer will reach the middle of the linked list.
This is how the middle node of a linked list can be accessed.
Java program to print the middle node of a linked list in Java
import java.util.*;
// program to print middle node of a linked list
public class LinkedList {
Node head; // head node of the linked list
/* node of the linked list which is having an int variable and a next pointer */
class Node {
int data;
Node next;
Node(int d) {
data = d;
next = null;
}
}
//method to print the middle node of linked list
void printMiddleNode() {
Node slowPtr = head; /* both slow and fast are pointing head node*/
Node fastPtr = head;
if (head == null) {
System.out.println("linked list does not exist");
}
while (fastPtr != null && fastPtr.next != null) {
fastPtr = fastPtr.next.next;
slowPtr = slowPtr.next;
}
System.out.println("The middle element is " +
slowPtr.data);
}
// append a new Node to the linked list.
public void append(int newdata) {
Node newnode = new Node( newdata);
if(head == null) {
head = newnode;
return;
}
newnode.next=null;
Node last = head;
while(last.next != null) {
last = last.next;
}
last.next = newnode;
return;
}
//method to print linked list
public void printLinkedList(){
Node curr = head;
while (curr != null){
if(curr.next == null) {
System.out.print(curr.data);
}
else {
System.out.print(curr.data+"->");
}
curr = curr.next;
}
}
public static void main(String [] args)
{
LinkedList list = new LinkedList();
list.append(10);
list.append(15);
list.append(12);
list.append(18);
list.append(20);
list.printLinkedList();
System.out.println();
list.printMiddleNode();
}
}
// Code is provided by Anubhav SrivastavaOutput:
10->15->12->18->20 The middle element is 12
Time complexity
Hence, the above approach finds the middle element of a linked list in O(n/2) time which is in general is O(n) time
Also learn:
Leave a Reply