• + 5 comments

    The tale isn't important.

    There is a "slow" pointer which moves one node at a time. There is a "fast" pointer which moves twice as fast, two nodes at a time.

    A visualization as slow and fast pointers move through linked list with 10 nodes:

    1: |sf--------|
    2: |-s-f------|
    3: |--s--f----|
    4: |---s---f--|
    5: |----s----f|
    

    At this point one of two things are true: 1) the linked list does not loop (checked with fast != null && fast.next != null) or 2) it does loop. Let's continue visualization assuming it does loop:

    6: |-f----s---|
    7: |---f---s--|
    8: |-----f--s-|
    9: |-------f-s|
    10: s == f
    

    If the linked list is not looped, the fast pointer finishes the race at O(n/2) time; we can remove the constant and call it O(n). If the linked list does loop, the slow pointer moves through the whole linked list and eventually equals the faster pointer at O(n) time.