# How to Find If Linked List Contains Loop or Cycle in Java - Coding Interview Question With Solution

Write a Java program to check if a linked list is circular or cyclic,  and how do you find if a linked list contains loop or cycles in Java are some common linked list relateasked in various Java Interviews. This is sometimes asked as follow-up question of basic linked list questions like inserting an element at the beginning, middle and end of a linked listrder to solve linked list related algorithmic questions in Java, you need to be familiar with the concept of singly linked list, doubly linked list, and circular linked list. Until stated specifically, most questions are based on a singly linked list. For those who are not familiar with the linked list data structure, its a collection of nodes.

Each node contains two parts data and address, where address part points to another node in a linked list. The last node of a linked list often referred to as tail points to null. Also, a single list can only move in one direction, towards the end.

Now, let's come back to this question. The good thing about this question is that it can also be solved by using two pointer approaches discussed ked list contains a loop or cycles it is known as a circular or cyclic linked list. As I said we can use two pointer approaches to check if a linked list is circular or not.

Also, basic knowledge of essential data structure is also very important and that's why I suggest all Java programmers join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.

## Algorithm to find if the linked list contains loops or cycles

Two pointers, fast and slow is used while iterating over the linked list. The fast pointer moves two nodes in each iteration, while slow pointer moves to one node. If the linked list contains loop or cycle than both fast and slow pointer will meet at some point during iteration. If they don't meet and fast or slow will point to null, then the linked list is not cyclic and it doesn't contain any loop. Here is the exact algorithm

1) Use two pointers fast and slow
2) Move fast two nodes and slow one node in each iteration
3) If fast and slow meet then linked list contains cycle
4) if fast points to null or fast.next points to null then linked list is not cyclic

Next section contains Java program to check if linked list contains loop or cycle, which is exact implementation of above algorithm. This algorithm is also knownd popularly known as tortoise and hare algorithm to find cycles in linked list.

### Java program to check if linked list is circular or not.

This Java program uses LinkedList(not java.util.LinkedList)  and Node class from previous example of Linked List, with modification of addinand appendToTail() method. Also, isCyclic() method of linked list is used to implement logic to find if linked list contains cycle or not. Subsequently isCyclic() returns true if linked list is cyclic otherwise it return false.

```/*
* Java class to represent linked list data structure.
*/
public class LinkedList {
private Node head;
public LinkedList() { this.head = new Node("head"); }
public Node head() { return head;}

public void appendIntoTail(Node node) {
Node current = head;

//find last element of LinkedList i.e. tail
while(current.next() != null){
current = current.next();
}
//appending new node to tail in LinkedList
current.setNext(node);
}

/*
* If singly LinkedList contains Cycle then following would be true
* 1) slow and fast will point to same node i.e. they meet
* On the other hand if fast will point to null or next node of
* fast will point to null then LinkedList does not contains cycle.
*/
public boolean isCyclic(){
Node fast = head;
Node slow = head;

while(fast!= null && fast.next != null){
fast = fast.next.next;
slow = slow.next;

//if fast and slow pointers are meeting then LinkedList is cyclic
if(fast == slow ){
return true;
}
}
return false;
}

@Override
public String toString(){
StringBuilder sb = new StringBuilder();
Node current = head.next();
while(current != null){
sb.append(current).append("-->");
current = current.next();
}
sb.delete(sb.length() - 3, sb.length()); // to remove --> from last node
return sb.toString();
}

public static class Node {
private Node next;
private String data;

public Node(String data) {
this.data = data;
}

public String data() { return data; }
public void setData(String data) { this.data = data;}

public Node next() { return next; }
public void setNext(Node next) { this.next = next; }

@Override
public String toString() {
return this.data;
}
}
}```

### Testing a linked list for cycle or loop

In this section we will test linked list usinith two linked lists, one contains cycle, and other is not cyclic. You can evenor isCyclic() method to test different linked list with circles and loops at different positions. Here is first test where linked list does not contain any cycle.
```/**
*
* Java program to find if LinkedList contains loop or cycle or not.
* This example uses two pointer approach to detect cycle in linked list.
* Fast pointer moves two node at a time while slow pointer moves one node.
* If linked list contains any cycle or loop then both pointer will meet some time.
*
* @author Javin Paul
*/
public class LinkedListTest {

public static void main(String args[]) {

//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
linkedList.appendIntoTail(new LinkedList.Node("101"));
linkedList.appendIntoTail(new LinkedList.Node("201"));
linkedList.appendIntoTail(new LinkedList.Node("301"));
linkedList.appendIntoTail(new LinkedList.Node("401"));

System.out.println("Linked List : " + linkedList);

if(linkedList.isCyclic()){
System.out.println("Linked List is cyclic as it contains cycles or loop");
}else{
System.out.println("LinkedList is not cyclic, no loop or cycle found");
}

}

}

Output:
Linked List : 101-->201-->301-->401
LinkedList is not cyclic, no loop or cycle found```

Now let's change the linked list so that it contains cycle or loop,
```//creating LinkedList with 5 elements including head
LinkedList linkedList = new LinkedList();
linkedList.appendIntoTail(new LinkedList.Node("101"));
LinkedList.Node cycle = new LinkedList.Node("201");
linkedList.appendIntoTail(cycle);
linkedList.appendIntoTail(new LinkedList.Node("301"));
linkedList.appendIntoTail(new LinkedList.Node("401"));
linkedList.appendIntoTail(cycle);

//don't call toString method in case of cyclic linked list, it will throw OutOfMemoryError
//System.out.println("Linked List : " + linkedList);

if(linkedList.isCyclic()){
System.out.println("Linked List is cyclic as it contains cycles or loop");
}else{
System.out.println("LinkedList is not cyclic, no loop or cycle found");
}

Output:
Linked List is cyclic as it contains cycles or loop```

Let me show you an interesting point here, in case you have not noticed already. This is also asked in interviews as, do you see anything suspicious? toString() method of LinkedList class is not checking for cycles or loop and it will throwif you try to print a linked list with cycles. Now, if you are really lucky then they may ask you to find start of loop in linked list. That's exercise for you, but let me give you a hint, look at below diagram of a linked list which contains cycle, red element is the start of cycle. What is special about it? If you look closely, you can see that it's the only node in whole linked list which is next node of other two pointers.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog
• Difference between array and linked list data structure? (answer)
• Difference between a binary tree and binary search tree? (answer)
• How to reverse a linked list in Java using iteration and recursion? (solution)
• How to reverse an array in place in Java? (solution)
• How to find all permutations of a String in Java? (solution)
• How to reverse a String in place in Java? (solution)
• How to remove duplicate elements from an array without using Collections? (solution)
• Top 5 Books on Data Structure and Algorithms for Java Developers (books)
• Top 5 books on Programming/Coding Interviews (list)

#### 20 comments :

D. Rajgoplachari said...

This same question of cycle detection in linked list is asked to me in Polaris Interview, I didn't know the trick of two pointers :(, Now it seems so easy.

Anonymous said...

Inside the while loop of isCyclic(), do you need to check whether fast is null after fast forward? like,
if(fast==null || fast == slow ){
return true;
}

Peter said...

@Anonymous, No, that's not correct, because if fast is null means linked list is not cyclic. But original code is also not correct and will throw NullPointerException if fast is null. Instead of just checking while(fast.next != null), it should check while(fast != null && fast.next != null), that way code will prevent NullPointerException. I think author, just missed this condition.

Ramesh V L said...

Javin,
Good post and helps many interviewees.
I think, a (fast == null) check is required as also pointed by @Anonymous. Otherwise, the next condition check at beginning of while loop will throw NPE if fast becomes null

Javin @ Sort Hashtable on values in Java said...

Hello @Ramesh, @Anonymous and @Peter, yes, fast== null check is missing in while loop, my bad. It's updated now. Thanks for pointing that.

Anonymous said...

For last exercise question, doubly linked list can be used to check loop. If parent pointer is not null it's already messed up.

Anonymous said...

the link list was circular but it said not circular
the data is like :
101-->201-->301-->401-->501-->601-->701-->201

Maruti said...

I think the best way to find the cycles is
traverse from the begining and check in map if the node pointer is in hashmap if present then its cyclic else put the node pointer and move to next.

if you reach till end and you didnt find any duplicate entry in hashmap/hashtable then its not cyclic.. correct me if I am wrong..

Anonymous said...

I was asked this ques on linked list..
Remove the current node from the list. Lets say there is a linked list as below
A1->A2->A3->A4->A5
the pointer is at A3. You have to delete the node A3 and you dont have the pointer to A2.

I still havent got the solution for that.
Little help here.. anyone ???

Kinshuk Chandra said...

Nice post - slow and fast pointer approach is the best. Here is my code from http://k2code.blogspot.in/2011/12/finding-start-of-loop-in-circular.html

/**
* Returns the node at the start of a loop in the given circular linked
* list. A circular list is one in which a node's next pointer points
* to an earlier node, so as to make a loop in the linked list. For
* instance:
*
* input: A -> B -> C -> D -> E -> C [the same C as earlier]
* output: C
*
*
* @param linkedList
* list to be tested
* @return the node at the start of the loop if there is a loop, null
* otherwise
*/
public static IntegerNode findLoopStart(LinkedList linkedList) {
if (linkedList == null || linkedList.getHead() == null) {
return null;
}

IntegerNode loopStartNode = null;
IntegerNode slow = linkedList.getHead();
IntegerNode fast = linkedList.getHead();

while (slow != null && fast != null) {
slow = slow.getNext();
if (fast.getNext() == null) {
loopStartNode = null;
break;
}
fast = fast.getNext().getNext();

// If slow and fast point to the same node, it means that the
// linkedList contains a loop.
if (slow == fast) {

slow = linkedList.getHead();

while (slow != fast) {
// Keep incrementing the two pointers until they both
// meet again. When this happens, both the pointers will
// point to the beginning of the loop
slow = slow.getNext(); // Can't be null, as we have a loop
fast = fast.getNext(); // Can't be null, as we have a loop
}

loopStartNode = slow;
break;
}
}

return loopStartNode;
}

Unknown said...

I was asked this ques on linked list..
Remove the current node from the list. Lets say there is a linked list as below
A1->A2->A3->A4->A5
the pointer is at A3. You have to delete the node A3 and you dont have the pointer to A2.

I still havent got the solution for that.
Little help here.. anyone ???

Answer :-
1) store value of A3 in some variable (temp).
2) copy the value of A4 to A3.
3) Delete the node A4 (can do that as we can refer to A4 and A5)
4) return temp

Anonymous said...

how can learn datastructures in java?

parag said...

@javin I have been asked in recent interview. why the fast pointer is move by 2 node not by 3 or 4 node.

Unknown said...

Back in the days in university a professor told me "if you have to interrupt a loop with a return statement, then you are not using the properly loop, nor the loop property"... So I took your code in order to make it match this corollary I was told by my professor.
static boolean hasCycle(LinkedList linkedList){
LinkedList.Node slow = linkedList.head().next();
LinkedList.Node fast = linkedList.head().next().next();
while(fast!=null && fast.next()!=null && fast!=slow){
fast = fast.next().next();
slow = slow.next();
}
return fast==slow;
}

Anonymous said...

Does this solution also known as Floyd's Cycle-Finding Algorithm for detecting cycle on linked list? I was to explain this algorithm on an Interview but I didn't know that two pointer algorithm is also known as Floyd's Cycle Finding algorithm. Please suggest if my understanding is correct.

javin paul said...

@Anonymous, yes you are correct. This fast and slow pointer approach is also known as Floyd's Cycle finding algorithm. One more name of this algorithm is "tortoise and hare" cycle detection algorithm.

Unknown said...

Copy the A4 data into A3 and remove A4(A3.next = A3.next.next)

Anonymous said...

Did anybody knows how to check if the linked list is circular without using head,tail or size of the linked list

UPSC General Topics contents said...

Hey what if Head is null? That case is not handled!

public static boolean findLoop(Node head) {
boolean retVal = false;
if(head != null) {
Node fst_ptr = head, slw_ptr = head;
while(fst_ptr != null && fst_ptr.next != null) {
fst_ptr = fst_ptr.next.next;
slw_ptr = slw_ptr.next;
if(slw_ptr == fst_ptr) {
retVal = true;
}
}
}
return retVal;
}

This is my code, please let me know where have I been wrong.

The program I have written seems to go in an infinite loop.

Thanks in advance!

Waqas Khan said...

why we need two pointers, we can use head for this, no need to move second pointer, if current pointer came back to head then there is a cycle
public void findCycle(){
Node current = head.next;

while(current.next != null){
if(current==head){
System.out.println("cycle exists");
break;
}
current = current.next;
}
}