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
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 :-
- Find whether linked list contains cycle or not.
- 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.
1 thought on “Find Starting Node of Cycle in Linked List | Linked List Problem”
What’s interesting is that this gives you the start of the cycle, but not the length. Brent’s algorithm does the opposite: Move the fast pointer one at a time; the slow pointer doesn’t move except it is set to match the fast pointer after 2, then after 4, then after 8, 16, 32 steps etc. Brent’s algorithm finds a point inside the cycle and tells you immediately the length of the cycle – but I cant figure out how to find the start of the cycle.