Find Starting Node of Cycle in Linked List | Linked List Problem

4 years ago Lalit Bhagtani 1

Problem Statement

You have given a singly linked list, return the node of the linked list where cycle begins. If there is no cycle, then return null.

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 

Linked List Cycle

Input :- head = [5, 4, 10, 15, 1], position = 2 (cycle begins at 2nd node)
Output :- Node(10)
Input :- head = [5, 4, 10, 15, 1, 5, 6], position = -1 (no cycle in linked list)
Output :- null

Solution

This problem can be solved in two steps :-

  1. Find whether linked list contains cycle or not.
  2. If linked list contains cycle, find the starting node 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 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.

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.

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();
		ListNode listNode = main.findStartNodeOfCycle(head);		
		System.out.print(listNode.value);
	}
	
	/* Solution */
	public ListNode findStartNodeOfCycle(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){            
            ListNode temp = head;
            while(temp != point){
                temp = temp.next;
                point = point.next;
            }
            return temp;            
        }        
        return null;
    }
	
	/* Definition of Linked List Node */
	public static class ListNode {		
		int value;
		ListNode next;
		
		public ListNode(int value) {
			this.value = value;
		}		
	}
}

Result

10

That’s all for Find Starting Node 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.