/** * Definition for singly-linked list. * class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */ public class Solution { public ListNode detectCycle(ListNode head) { if(head == null || head.next == null) return null; ListNode fast = head; ListNode slow = head; //checking if cycle is present while(fast!= null && fast.next != null){ fast = fast.next.next; slow = slow.next; if(fast == slow) break; } if(fast != slow) return null; //cycle is present now fast and slow will be at meeting point // now we will keep slow at head again and move them at together at one unit speed only to find the // the starting cycle node slow = head; //fast = fast; while(fast != slow){ slow = slow.next; fast = fast.next; } //now they are at the starting cyclic node return slow; //we can also find A , B+C , m' using the equation now } }
Preview:
downloadDownload PNG
downloadDownload JPEG
downloadDownload SVG
Tip: You can change the style, width & colours of the snippet with the inspect tool before clicking Download!
Click to optimize width for Twitter