In this post we’ll see how to detect a loop or cycle in a linked list using a Java program and how to remove that loop in a linked list.
Linked list loop detection
If there is a loop in a linked list that means one of the node references back to any of the previous nodes rather than referencing the next node or null. Traversing a linked list with loop will cycle back to the old node rather than concluding its traversal once null is reached causing an infinite loop.
Following image shows how a linked list with a loop looks like.
Linked list loop detection Java program
There are various options for writing a Java program for linked list loop detection.
One of the approach is to use HashSet where you add each traversed node of the linked list to the HashSet, if the same node is encountered again trying to add will return false indicating a loop. But this approach requires extra space as another data structure HashSet is used.
The implementation which is widely used for linked list loop detection is Floyd's cycle-finding algorithm also known as "tortoise and the hare" algorithm. This implementation doesn’t require auxiliary space so space complexity is O(1) and time complexity is O(n) as linear traversal of the linked list is done.
Steps for implementing this algorithm are as follows-- Use 2 references which are initialized to the head of the linked list.
- One of them hop a node and the other takes two hops in each iteration.
- If both of these references point to the same node at some iteration that means there is a loop.
- If any of these references reach null that means there is no loop in the linked list.
public class SinglyLinkedList {
private Node head;
SinglyLinkedList(){
head = null;
}
static class Node{
//data
int i;
Node next;
Node(int i){
this.i = i;
this.next = null;
}
}
// Method to add nodes to linked list
public void insertLast(Node newNode){
if(isEmpty()){
head = newNode;
}else{
Node current = head;
// traverse to the last of the list
while(current.next != null){
current = current.next;
}
// adding new node, current last node
// starts referencing to this new node
current.next = newNode;
}
}
public boolean isEmpty(){
return head == null;
}
public boolean isLoopDetected(){
Node fast, slow;
// start from head
fast = slow = head;
while(slow != null && fast != null && fast.next != null){
// hops two references
fast = fast.next.next;
// hops one reference
slow = slow.next;
if(fast == slow){
return true;
}
}
return false;
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
Node node = new Node(30);
list.insertLast(new Node(10));
list.insertLast(new Node(20));
list.insertLast(node);
list.insertLast(new Node(40));
list.insertLast(new Node(50));
// same node inserted again to create loop
list.insertLast(node);
System.out.println("Loop detected? " + list.isLoopDetected());
}
}
Output
Loop detected? True
Removing loop in linked list
In order to remove a loop in linked list three steps are required.
- First is of course to check whether a loop exists in a linked list or not.
- If a loop exists then both pointers will meet at some node. From there you will have to find the start node of the loop. For doing that set one of the pointers to the head and the other one remains at the point where both pointers met. From there move both of them sequentially (one reference at a time). The node where both these reference meet again would be the start of the loop.
- Once both slow and fast pointers are at the beginning of the loop if you move fast by one reference at a time
ultimately it will again become equal to slow as it will cycle back because of the loop. That location of the fast where
it becomes equal to the slow again is the end node of the loop.
To remove loop in the liked list just set the next to null for the node referenced by fast.
public class SinglyLinkedList {
private Node head;
SinglyLinkedList(){
head = null;
}
static class Node{
//data
int i;
Node next;
Node(int i){
this.i = i;
this.next = null;
}
public void displayData(){
System.out.println("i= " + i);
}
}
// Method to add nodes to linked list
public void insertLast(Node newNode){
if(isEmpty()){
head = newNode;
}else{
Node current = head;
// traverse to the last of the list
while(current.next != null){
current = current.next;
}
// adding new node, current last node
// starts referencing to this new node
current.next = newNode;
}
}
public boolean isEmpty(){
return head == null;
}
public Node findStartOfLoop(){
Node fast, slow;
fast = slow = head;
boolean loopFlag = false;
// to check for loop
while(slow != null && fast != null && fast.next != null){
fast = fast.next.next;
slow = slow.next;
if(fast == slow){
loopFlag = true;
break;
}
}
// Find start of the loop
if(loopFlag){
System.out.println("Loop detected in liked list, finding start of the loop..");
slow = head;
while(slow != fast){
slow = slow.next;
fast = fast.next;
}
}else{
System.out.println("No Loop detected in the linkedlist");
fast = null;
}
return fast;
}
public void removeLoop(Node startNode){
Node fast, slow;
fast = slow = startNode;
while(fast.next != slow){
fast = fast.next;
}
fast.next = null;
}
// Method to traverse and display all nodes
public void displayList(){
Node current = head;
while(current != null){
current.displayData();
current = current.next;
}
}
public static void main(String[] args) {
SinglyLinkedList list = new SinglyLinkedList();
Node node = new Node(30);
list.insertLast(new Node(10));
list.insertLast(new Node(20));
list.insertLast(node);
list.insertLast(new Node(40));
list.insertLast(new Node(50));
// same node inserted again to create loop
list.insertLast(node);
Node loopStartNode = list.findStartOfLoop();
System.out.println("Start node of the loop- " + loopStartNode.i);
list.removeLoop(loopStartNode);
list.displayList();
}
}
Output
Loop detected in liked list, finding start of the loop.. Start node of the loop- 30 i= 10 i= 20 i= 30 i= 40 i= 50
In the code initially start node of the loop is searched and using that end node is searched. Once the end node of the loop is found its next reference is changed to null. Now the list can be traversed with going into an infinite loop.
That's all for this topic Java Program to Detect And Remove Loop in a Linked List. If you have any doubt or any suggestions to make please drop a comment. Thanks!
>>>Return to Java Programs Page
Related Topics
You may also like-
No comments:
Post a Comment