Code Destine

Problem Statement

You have given a singly linked list, find out if it contains a cycle or not.

Example 

Input :- head = [5, 4, 10, 15, 1, 7], Cycle at 3rd Node
Output :- true

Input :- head = [5, 4, 10, 15, 1, 5, 6], No Cycle
Output :- false

Solution

Floyd’s Cycle-Finding Algorithm can be used to solve this problem. This algorithm uses two variables that move at different speeds and if there is a cycle, both of the variables would point to the same value at some point in the future.

Create two variables fast and slow, then move both variables together, fast by two nodes and slow by one node till the fast variable reaches the last node or end of the linked list. If fast and slow variable points to the same node before the end of the while loop, then there is a cycle in the linked list otherwise there is no cycle.

Program

public class Main {

	public static void main(String[] args) {
		
		ListNode head = null;
		
		ListNode node = new ListNode(5);
		head = node;		
		node.next = new ListNode(4);
		node = node.next;	
		
		ListNode node10 = new ListNode(10);
		node.next = node10;
		node = node.next;
		
		node.next = new ListNode(15);
		node = node.next;		
		node.next = new ListNode(1);
		node = node.next;
		node.next = new ListNode(7);
		node = node.next;
		node.next = node10;
		
		Main main = new Main();
		boolean result = main.hasCycle(head);		
		System.out.print(result);
	}
	
	/* Solution */
	public boolean hasCycle(ListNode head) {
	     
        ListNode slow = head;
        ListNode fast = head;
        
        while(fast != null && fast.next != null){            
            slow = slow.next;
            fast = fast.next.next;
            if(slow == fast){
                return true;
            }
        }
        return false;
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

true

That’s all for Cycle in Linked List in Java, If you liked it, please share your thoughts in a comments section and share it with others too.