142. Linked List Cycle II

二刷 08/2022

Version #1 Floyd's Tortoise and Hare

------a-------x-----b-------

                   |                   |

                   -------c-------

搜287看证明

Time O(N)

Space O(1)

Runtime: 1 ms, faster than 58.84% of Java online submissions for Linked List Cycle II.

Memory Usage: 45 MB, less than 63.18% of Java online submissions for Linked List Cycle II.

public class Solution {

    public ListNode detectCycle(ListNode head) {

        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {

            slow = slow.next;

            fast = fast.next.next;

            if (slow == fast) {

                break;

            }

        }

        if (fast == null || fast.next == null) {

            return null;

        }

        slow = head;

        while (slow != fast) {

            slow = slow.next;

            fast = fast.next;

        }

        return slow;

    }

}

一刷
Proof

I have seen the accepted answer as proof elsewhere too. However, while its easy to grok, it is incorrect. What it proves is

x=z$x=z$ (which is obviously wrong, and the diagram just makes it seem plausible due to the way it is sketched).

What you really want to prove is (using the same variables as described in the diagram in the accepted answer above):

z=x mod (y+z)$z=xmod(y+z)$

(y+z)$(y+z)$ is the loop length, L$L$

so, what we want to prove is:

z=x mod L$z=xmodL$

Or that z is congruent to x (modulo L)

Following proof makes more sense to me:

Meeting point, M=x+y$M=x+y$

2(x+y)=M+kL$2(x+y)=M+kL$, where k$k$ is some constant. Basically, distance travelled by the fast pointer is x+y$x+y$ plus some multiple of loop length, L$L$

x+y=kL$x+y=kL$

x=kL−y$x=kL-y$

The above equation proves that x$x$ is the same as some multiple of loop length, L$L$ minus y$y$. So, if the fast pointer starts at the meeting point, M$M$ or at x+y$x+y$, then it will end up at the start of the loop.

x = kL - y = (k+1)L + (L-y) = (k+1)L + z
-> x % L = z

53.34 %
public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
            if (slow == fast) {
                break;
            }
        }
        if (fast == null || fast.next == null) {
            return null;
        }
        slow = head;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }
}