O(n) solution by using two pointers without change anything


  • 196
    W

    my solution is like this: using two pointers, one of them one step at a time. another pointer each take two steps. Suppose the first meet at step k,the length of the Cycle is r. so..2k-k=nr,k=nr
    Now, the distance between the start node of list and the start node of cycle is s. the distance between the start of list and the first meeting node is k(the pointer which wake one step at a time waked k steps).the distance between the start node of cycle and the first meeting node is m, so...s=k-m,
    s=nr-m=(n-1)r+(r-m),here we takes n = 1
    ..so, using one pointer start from the start node of list, another pointer start from the first meeting node, all of them wake one step at a time, the first time they meeting each other is the start of the cycle.

        ListNode *detectCycle(ListNode *head) {
        if (head == NULL || head->next == NULL) return NULL;
        
        ListNode* firstp = head;
        ListNode* secondp = head;
        bool isCycle = false;
        
        while(firstp != NULL && secondp != NULL) {
            firstp = firstp->next;
            if (secondp->next == NULL) return NULL;
            secondp = secondp->next->next;
            if (firstp == secondp) { isCycle = true; break; }
        }
        
        if(!isCycle) return NULL;
        firstp = head;
        while( firstp != secondp) {
            firstp = firstp->next;
            secondp = secondp->next;
        }
    
        return firstp;
    }

  • 1
    S

    Thanks for your post. However it would be better to share solution with correct code format and elaborated thoughts. Please read the Discuss FAQ for more info. Take a look at good sharing example


  • 0
    F
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 2
    S

    Well, I draw a picture, and understand your solution finally, it's more like a mathematics problem......


  • 1
    P

    it does look like a brain teaser.


  • 7
    F

    you are so newbee, so diao!!!!!


  • 0
    L
    This post is deleted!

  • 0
    S
    This post is deleted!

  • 0
    L
    This post is deleted!

  • 15
    K

    The same idea implemented by python. Actually there is a famous algorithm for this: Floyd's cycle detection algorithm, also known as the hare-tortoise algorithm.

    class Solution:
        # @param head, a ListNode
        # @return a list node
        def detectCycle(self, head):
            if head == None: return None
            hare, turtle= head, head
            while hare != None:
                turtle = turtle.next
                hare = hare.next
                if hare == None: return None
                hare = hare.next
                if hare == turtle:
                    turtle = head
                    while turtle != hare:
                        hare = hare.next
                        turtle = turtle.next
                    return hare
            return None
    

  • 0
    H

    perfect answer


  • 0
    C

    ..............


  • 0
    C

    My java version with the same idea:

    > public class Solution {
    >         public ListNode detectCycle(ListNode head) {
    >             if(head==null || head.next==null) return null;
    >             ListNode pointer1,pointer2,pointer3;
    >             pointer1=pointer2=pointer3=head; Boolean inited=false;
    >             for(;pointer2!=null;){
    >                 pointer1=pointer1.next;
    >                 pointer2=pointer2.next;
    >                 if(pointer2==null) return null;
    >                     else pointer2=pointer2.next;
    >                 if(pointer1==pointer2 && inited ) break;
    >                 if(!inited) inited=true;
    >             }
    >             if(pointer2==null) return null;
    >             while(pointer1!=pointer3){
    >                 pointer1=pointer1.next;
    >                 pointer3=pointer3.next;
    >             }
    >             return pointer1;
    >             
    >         }
    > 
    > }

  • 0
    X
    This post is deleted!

  • 43
    R

    Just make a easier understanding.
    Suppose the first meet at step k,the distance between the start node of list and the start node of cycle is s, and the distance between the start node of cycle and the first meeting node is m. Then 2k = (s + m + n1r) = 2(s + m + n2r) ==> s + m = nr. Steps moving from start node to the start of the cycle is just s, moving from m by s steps would be the start of the cycle, covering n cycles. In other words, they meet at the entry of cycle.


  • 0
    C

    I can't agree more.


  • 7

    Smart solution. But replacing all "wake" to "walk" in your words makes me feel better :) Another minor point is you can't just "here we takes n = 1" even it doesn't affect the last result. It still should read as s=nr-m. That means the 1st pointer starts from beginning of the list while the 2nd pointer starts from meet point, they will meet in the cycle point but the 2nd pointer walked n times of the cycle.


  • 1
    Y

    I agree with you. we may not assume n = 1 here. This point confuses me for a long time until I see your explanation.


  • 0
    J

    Interesting view!


Log in to reply
 

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