Clean Java Solution

  • 0

    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.

    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 || == null) {
                    // no cycle, return null
                    return null;
                slowRunner =;
                fastRunner =;
                if(slowRunner == fastRunner) {
                    // slowRunner and fastRunner will collide at (k%l) steps behind the cycle start
            fastRunner = head;
            while(slowRunner != fastRunner) {
              slowRunner =;
              fastRunner =;
            return fastRunner;

Log in to reply

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