In this Data structures tutorial we will to find out whether our Singly Linked List is circular or not in java.
For finding out whether our Singly Linked List is circular or not in java we will keep two pointers(as used in diagrom below) :
slowPointer: will step over LinkedList by 1 Node.
fastPointer: will step over LinkedList by 2 Node.
Eventually, if Singly LinkedList is circular pointers will meet at certain point.(Let’s call that point meeting point)
Important methods used to find out whether our Singly Linked List is circular or not in java are as follows>
>findCircularOrNot()
Logic explanation to find out whether our Singly Linked List is circular or not in java with diagram >
Let’s see concept of slowPointer and fastPointer in finding out whether Singly LinkedList is circular or not in java with diagram.
Below we have shown meeting point of above circular LinkedList.
Example(considering above diagram)>
NOW WE HAVE TO FIND OUT WHETHER LIST IS CIRCULAR OR NOT.
slowPointer (steps 1node)
|
fastPointer (steps 2node)
|
start at 11
|
start at 11
|
>reaches 22
|
>reaches 33
|
>reaches 33
|
>reaches 55
|
>reaches 44
|
>reaches 33
|
>reaches 55 (meeting point)
|
>reaches 55 (meeting point)
|
Full Program/SourceCode/Example to find out whether our Singly Linked List is circular or not in java >
/**
*Node class, which holds data and contains next which points to next Node.
*/
class Node {
public int data; // data in Node.
public Node next; // points to next Node in list.
/**
* Constructor
*/
public Node(int data){
this.data = data;
}
/**
* Display Node's data
*/
public void displayNode() {
System.out.print( data + " ");
}
}
/**
* LinkedList class
*/
class LinkedList{
Node first=null;
Node circularPoint1; //points used to make LinkedList circular.
Node circularPoint2;
Node slowPointer; //will step over LinkedList by 1 Node.
Node fastPointer; //will step over LinkedList by 2 Node.
/**
* Insert New Node at first position
*/
public void insert(int data){
Node newNode=new Node(data);
newNode.next=first;
first=newNode;
/*
* Below we have kept track of two Nodes so that later we can make LinkedList circular(If required).
* Note:- I have kept track of below two nodes just for demonstration purpose. You may provide some other implementation for making LinkedList circular.
*/
if(data==33)
circularPoint1=newNode;
if(data==66)
circularPoint2=newNode;
}
/**
*This method makes LikedList circular- by making end Node point to some middle Node of LinkedList.
*end Node--->middle Node.
*/
public void makeLinkedListCircular(){
circularPoint2.next=circularPoint1;
System.out.println("LinkedList has been succesfully converted into CircularLinkedList");
}
/**
* method finds out whether LinkedList is circular or not?
*/
public void findCircularOrNot(){
slowPointer=first;
fastPointer=first;
while( (slowPointer!=fastPointer || slowPointer==first) //when first time condition is checked slowPointer is equal to fastPointer -so that does not means LinkedList is circular and we exit while loop
//we got to be cautious by keeping extra check that whether we are on first node or not.
&& fastPointer.next!=null //used to avoid NullPointerException(in case we are are on last Node- than next is null, calling further next on null will cause NPE.)
&& fastPointer.next.next!=null){
slowPointer=slowPointer.next; // step over LinkedList by 1 Node.
fastPointer=fastPointer.next.next; // step over LinkedList by 2 Node.
}
if(slowPointer==fastPointer)
System.out.println("LinkedList is CIRCULAR");
else
System.out.println("LinkedList is NOT CIRCULAR");
}
/**
* Display LinkedList
*/
public void displayLinkedList(){
Node tempDisplay=first;
int displayLimiterCtr=0; //as our LinkedList is circular it will keep on displaying nodes till infinity...
//so this variable will help us in limiting the display to specific count.
System.out.print("Displaying LinkedList [first--->last]: ");
while(tempDisplay!=null){
tempDisplay.displayNode();
tempDisplay=tempDisplay.next;
if(++displayLimiterCtr >= 12) //stops displaying after 12 Nodes.
break;
}
System.out.println();
}
}
/** Copyright (c), AnkitMittal www.JavaMadeSoEasy.com */
/**
* Main class - To test LinkedList is circular or not.
*/
public class LinkedListFindCircular {
public static void main(String[] args) {
LinkedList linkedList=new LinkedList();
linkedList.insert(66);
linkedList.insert(55);
linkedList.insert(44);
linkedList.insert(33);
linkedList.insert(22);
linkedList.insert(11);
linkedList.displayLinkedList();
linkedList.findCircularOrNot();
System.out.println();
linkedList.makeLinkedListCircular();
linkedList.displayLinkedList();
linkedList.findCircularOrNot();
}
}
/*OUTPUT
Displaying LinkedList [first--->last]: 11 22 33 44 55 66
LinkedList is NOT CIRCULAR
LinkedList has been succesfully converted into CircularLinkedList
Displaying LinkedList [first--->last]: 11 22 33 44 55 66 33 44 55 66 33 44
LinkedList is CIRCULAR
*/
|
Once we have converted our LinkedList into circular one by using are makeLinkedListCircular() method, we are able to detect so by our algorithm as well.
So we wrote java program to find out whether our Singly Linked List is circular or not in java.
So in this Data structures tutorial we learned important java interview question how to find/detect whether our Singly Linked List is circular or not in java.
Having any doubt? or you you liked the tutorial! Please comment in below section.
Please express your love by liking JavaMadeSoEasy.com (JMSE) on facebook, following on google+ or Twitter.
RELATED LINKS>
1) Stacks, Queues in Data Structures in java
2) Single LinkedList implementations in Data Structures in java:-
>
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
Sorted Singly LinkedList(Singly LinkedList) custom implementation - insert Nodes in between in java
3) Doubly LinkedList implementations in Data Structures in java:-
4)Implement Stack, Queue using LinkedList
5) Some of the tricky and interesting Single LinkedList implementations in Data Structures in java
6) Binary tree tutorial in java >