Java O(1) space solution with detailed explanation.


  • 87
    Q

    Define two pointers slow and fast. Both start at head node, fast is twice as fast as slow. If it reaches the end it means there is no cycle, otherwise eventually it will eventually catch up to slow pointer somewhere in the cycle.

    Let the distance from the first node to the the node where cycle begins be A, and let say the slow pointer travels travels A+B. The fast pointer must travel 2A+2B to catch up. The cycle size is N. Full cycle is also how much more fast pointer has traveled than slow pointer at meeting point.

    A+B+N = 2A+2B
    N=A+B
    

    From our calculation slow pointer traveled exactly full cycle when it meets fast pointer, and since originally it travled A before starting on a cycle, it must travel A to reach the point where cycle begins! We can start another slow pointer at head node, and move both pointers until they meet at the beginning of a cycle.

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

  • 0
    Z

    why it is O(n) Space? tpyo? O(n) Time
    in your code, you don't use extra space.


  • 0
    Q

    yes it's typo O(1) space. Corrected


  • 0
    H
    This post is deleted!

  • 2
    O

    I dont understand how will slow2 reach slow ? they move with the same rate


  • 0
    L

    since slow is already in the loop, so slow can only move inside the loop. While slow2 just moves from the beginning. Thus they will meet exactly at the beginning of cycle.


  • 5
    X

    The N maybe more than one circle size.But the equation is true.


  • 0
    J

    I can't understand the formula very well
    A+B+N = 2A+2B
    N=A+B
    Think about the LikedList: 1->2->3->4->5->6->7->8->9->10-> the cycle begin 3. The slow pointer and fast pointer will meet at 9,


  • 1
    Q

    N = A + B
    Here
    A = 2 (1->3),
    N = 8 (from 3->10 + 10->3),
    B = N-A = 6,
    Meeting point is A+B = 2+6=8 (8th node from start which is 9)


  • 1
    J

    If you meet at node 7, how can the slow meet the slow2 at node 3? from node 1 to 3 is two steps, from node 7-3 is four steps


  • 0
    Q

    I corrected my explanation right after clicking 'Add Comment'


  • 142
    L

    Is this diagram help you understand?
    When fast and slow meet at point p, the length they have run are 'a+2b+c' and 'a+b'.
    Since the fast is 2 times faster than the slow. So a+2b+c == 2(a+b), then we get 'a==c'.
    So when another slow2 pointer run from head to 'q', at the same time, previous slow pointer will run from 'p' to 'q', so they meet at the pointer 'q' together.
    enter image description here

    ListNode fast = head, slow = head;
    while(fast != null && fast.next != null){
    fast = fast.next.next;
    slow = slow.next;
    if (fast == slow){
    ListNode slow2 = head;
    while (slow != slow2){
    	slow2 = slow2.next;
    	slow = slow.next;
    	 }
    	return slow;
    	}
    }
    return null;
    

  • 0
    J

    Note: a==c and clockwise for pre slow


  • 0
    V

    Since there is a cycle, when slow1 moves, it will loop from p to q while the slow2 moves from head to the q. And from the proof, we know that a==c, that means, the slow1 and slow2 will meet at the point which the cycle starts.


  • 0
    M

    This is actually called the Tortoise and Hare algorithm (in reference to Aesop's fable) and is attributed to Floyd, the same Floyd as the Floyd–Warshall algorithm, in case you were interested in more research.


  • 0
    S

    very clear! thanks!


  • 0

    Thanks friend, you really made it easy to understand!


  • 0
    B

    Cute draw! Thanks!


  • 7
    R

    actually it should be nN + A + B = 2(A + B).


  • 1
    C

    @lwen8989gmail.com The picture really helps! thanks a lot!


Log in to reply
 

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