How can you know if a linked list is not circular has an end )?

Check if a linked list is Circular Linked List

Given a singly linked list, find if the linked list is circular or not. A linked list is called circular if it is not NULL-terminated and all nodes are connected in the form of a cycle. Below is an example of a circular linked list.

An empty linked list is considered as circular.
Note that this problem is different from cycle detection problem, here all nodes have to be part of cycle.

1. Introduction

In Computer Science, a linked list is a linear data structure in which a pointer in each element determines the order.

In this tutorial, we’ll show how to check if a linked list is a circular linked list.

Algorithm to find if the linked list contains loops or cycles

Two pointers, fast and slow are used while iterating over the linked list. The fast pointer moves two nodes in each iteration, while the slow pointer moves to one node. If the linked list contains a loop or cycle then both fast and slow pointers 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 the linked list contains a cycle

4) if fast points to null or fast.next points to null then linked list is not cyclic

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

Java program to check if the 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 adding toString() method and 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 the linked list using Java main method with two linked lists, one contains a cycle, and the other is not cyclic. You can even write JUnit test cases for isCyclic() method to test different linked lists with circles and loops at different positions. Here is first test where the 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 loops and it will throw Exception in thread "main" java.lang.OutOfMemoryError: Java heap space, if you try to print a linked list with cycles.

Now, if you are really lucky then they may ask you to find the start of the loop in the linked list. That's an exercise for you, but let me give you a hint, look at the below diagram of a linked list that contains a cycle, the red element is the start of the cycle. What is special about it? If you look closely, you can see that it's the only node in the whole linked list which is the next node of the other two pointers.

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 a 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)

C++

// C++ program to check if linked list is circular #include<bits/stdc++.h> using namespace std; /* Link list Node */ struct Node { int data; struct Node* next; }; /* This function returns true if given linked list is circular, else false. */ bool isCircular(struct Node *head) { // An empty linked list is circular if (head == NULL) return true; // Next of head struct Node *node = head->next; // This loop would stope in both cases (1) If // Circular (2) Not circular while (node != NULL && node != head) node = node->next; // If loop stopped because of circular // condition return (node == head); } // Utility function to create a new node. Node *newNode(int data) { struct Node *temp =new Node; temp->data = data; temp->next = NULL; return temp; } /* Drier program to test above function*/ int main() { /* Start with the empty list */ struct Node* head = newNode(1); head->next = newNode(2); head->next->next = newNode(3); head->next->next->next = newNode(4); isCircular(head)? cout <<"Yes " : cout <<"No " ; // Making linked list circular head->next->next->next->next = head; isCircular(head)? cout <<"Yes " : cout <<"No " ; return 0; }

/div>