Code Destine

Problem Statement

You have given a singly linked list, return the length of cycle in the linked list. If there is no cycle, then return 0.

Note :- Cycle in the given linked list is represented by an integer position, which represents the position (0-indexed)  in the linked list where the cycle begins. If position is -1, then there is no cycle in the linked list.

Example 

Input :- head = [5, 4, 10, 15, 1, 7], position = 2 (cycle begins at 2nd node)
Output :- 4

Input :- head = [5, 4, 10, 15, 1, 5, 6], position = -1 (no cycle in linked list)
Output :- 0

Solution

This problem can be solved in three steps :-

1. Find whether linked list contains cycle or not.
2. If linked list contains cycle, find the starting node of cycle.
3. Once starting node is found, find the length of cycle.

Step 1 :- Floyd’s Cycle-Finding Algorithm can be used to solve the first step. 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, for more information see this post.

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 variables point 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.

Step 2 :- Once the fast and slow variables point to the same node, then set one of them to the head of the Linked List. Now move both of the variables at the same speed. The node where they meet again would be the starting node of the cycle, for more information see this post.

Step 3 :- Once the starting point of the cycle is found, keep one variable to the starting point and move another variable by the speed of one node. Create a new variable length and every time when a variable moves to the next node, increment it by 1. When both variables point to the same node, return the value of the length variable.

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();
		int length = main.findLengthOfCycle(head);		
		System.out.print(length);
	}
	
	/* Solution */
	public int findLengthOfCycle(ListNode head) {
	     
        ListNode point = null;
        ListNode fast = head;
        ListNode slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow =slow.next;
            if(fast == slow){
                point = fast;
                break;
            }
        }        
        
        if(point != null){            
            slow = head;
            while(slow != fast){
            	fast = fast.next;
                slow =slow.next;                
            }
            
            int length = 0;
            do {
            	slow = slow.next;
            	length++;
            }while(slow != fast);
            return length;
        }        
        
        return 0;
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

4

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