Clean Java Solution


  • 0
    W

    Suppose the length(head)=k+l, where l is the length of the cycle.
    Then the slowRunner and fastRunner will intersect at k%l steps behind the cycle start.

    Proof:
    After k iterations, slowRunner is at the cycle start and fastRunner is k%l steps ahead of slowRunner or l-(k%l) steps behind slowRunner.
    Then, after another l-(k%l) iterations, slowRunner and fastRunner collides. At this point, slowRunner is l-(k%l) steps ahead of the cycle start or l-(l-k%l) steps behind cycle start.
    But l-(l-k%l)=k%l so slowRunner and fastRunner collides at k%l steps behind the cycle start.

    Now, reset fastRunner to head and let the runners moves at same speed, they will collide after k steps, which is exactly the cycle start.

    public class Solution {
        public ListNode detectCycle(ListNode head) {
            ListNode slowRunner = head;
            ListNode fastRunner = head;
            
            for(;;) {
                if(fastRunner == null || fastRunner.next == null) {
                    // no cycle, return null
                    return null;
                }
                slowRunner = slowRunner.next;
                fastRunner = fastRunner.next.next;
                if(slowRunner == fastRunner) {
                    // slowRunner and fastRunner will collide at (k%l) steps behind the cycle start
                    break;
                }
            }
            
            fastRunner = head;
            while(slowRunner != fastRunner) {
              slowRunner = slowRunner.next;
              fastRunner = fastRunner.next;
            }
            return fastRunner;
        }
    }
    

Log in to reply
 

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