O(n) solution using Flyod's Cycle detection algorithm also known as Hare-Tortoise algorithm


  • 0
    A
    public ListNode detectCycle(ListNode head) {
            if(head == null || head.next == null)
                return null;
            ListNode hare = head; // slow iterator
            ListNode tortoise = head; // fast iterator
            boolean hasCycle = false;
            
            while(hare.next != null && hare.next.next != null) {
                tortoise = tortoise.next; // Move one step
                hare = hare.next.next; // Move two steps
                
                if(tortoise == hare) {
                    hasCycle = true;
                    break;
                }
            }
            
            if(!hasCycle)
                return null;
            hare = head;
            while(hare != tortoise) {
                hare = hare.next;
                tortoise = tortoise.next;
            }
            return hare;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.