Linked List: Circular Linked List?

Question: Write a function isCircular() which checks whether a linked list is circular or not.

package additional_problems.linkedList;

/**
 * Created by aarushi on 29/6/21.
 */
public class P06CheckCircular {
    public static void main(String[] args){
      	//create linked list
        LinkedList list= new LinkedList();
        ListNode node= new ListNode(4);
        list.add(node);
        node= new ListNode(6);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        //node at which the circle starts 
        ListNode nodeJoin= new ListNode(8);
        list.add(nodeJoin);
        node= new ListNode(9);
        list.add(node);
        node= new ListNode(10);
        list.add(node);
        node= new ListNode(18);
        list.add(node);
        node= new ListNode(20);
        list.add(node);
        node.setNext(nodeJoin);

        if(isCircular(list)){
            System.out.println("List is circular");
        } else {
            System.out.println("List is not circular");
        }
    }

    //method to check whether is linked list is circular or not
    public static boolean isCircular(LinkedList list){
        //initialize two pointers point 1 and point 2
        ListNode pointer1= list.head;
        ListNode pointer2= list.head;

        while (pointer1!=null && pointer2!=null){
            //increase pointer1 by one and pointer2 two nodes
            pointer1=pointer1.getNext();
            pointer2=pointer2.getNext().getNext();
            //if the list is circular the two pointers will meet at some node
            if(pointer1==pointer2 && pointer1!=null && pointer2!=null){
                return true;
            }
        }
        return false;
    }

}
package additional_problems.linkedList;

/**
 * Created by aarushi on 24/6/21.
 */
public class LinkedList {
    //data fields
    //head node
    ListNode head;

    //constructor to initialize head node
    public LinkedList() {
        head = null;
    }

    //function to add node to the end of the linked list
    public void add(ListNode node) {
        //if list is empty then set head equal to the node
        if (head == null) {
            head = node;
            node.setNext(null);
        } else {
            //create a pointer- temp
            ListNode temp = head;
            //iterate to the last element
            while (temp.getNext() != null) {
                temp = temp.getNext();
            }
            //insert the node at the end of the list
            temp.setNext(node);
            node.setNext(null);
        }
    }

    //method to delete the last node of the linked list
    public void delete(ListNode node) throws Exception {

        //throw exception if the list is empty
        if (head == null) {
            throw new Exception("List is empty");
        }

        //if the node passed is the head node then change the head pointer to the next node
        else if (node == head) {
            System.out.println(head.getData() + " deleted");
            head = head.getNext();
        } else {
            //pointer temp which will traverse the linked list
            ListNode temp = head;

            //find the node which points to the node to be deleted
            while (temp.getNext() != node && temp != null) {
                temp=temp.getNext();
            }

            //if node if found then delete the node otherwise throw an exception
            if (temp != null) {
                System.out.println(temp.getNext().getData() + " deleted");
                temp.setNext(node.getNext());
            } else {
                throw new Exception("Node not found");
            }

        }
    }

    public void printNoException() {
        if (head == null) {
            return;
        } else {
            ListNode temp = head;
            while (temp != null) {
                System.out.print(temp.getData() + " ");
                temp = temp.getNext();
            }
            System.out.println();
        }
    }

  

}
package additional_problems.linkedList;

/**
 * This class is the type declaration for a linked list
 * Created by aarushi on 24/6/21.
 */
public class ListNode {
    //data fields
    private int data; //stores the value of the node
    private ListNode next; //stores the reference of the next node

    //constructor to initialize the value of the node
    public ListNode(int data){
        this.data= data;
        this.subList=null;
    }

    //accessor method to get the value stored in data
    public int getData() {
        return this.data;
    }

    //mutator method to change the value of data
    public void setData(int data) {
        this.data = data;
    }

    //accessor method which returns the reference of the next node
    public ListNode getNext() {
        return this.next;
    }

    //mutator method which changes the reference of the next node
    public void setNext(ListNode next) {
        this.next = next;
    }

}

Leave a Reply

PHP JS HTML CSS BASH PYTHON CODE

Your email address will not be published.

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: