O(1) Space Solution


  • 169
    public boolean hasCycle(ListNode head) {
        if(head==null) return false;
        ListNode walker = head;
        ListNode runner = head;
        while(runner.next!=null && runner.next.next!=null) {
            walker = walker.next;
            runner = runner.next.next;
            if(walker==runner) return true;
        }
        return false;
    }
    
    1. Use two pointers, walker and runner.
    2. walker moves step by step. runner moves two steps at time.
    3. if the Linked List has a cycle walker and runner will meet at some
      point.

  • 0
    R

    Nice. That's very smart.


  • 0
    B

    This is wonderful, thanks very much!


  • 4
    D

    but how to prove this method mathmatically?


  • 0
    J

    What if runner.next is null? Still OK in Java?


  • 0
    K

    while(runner.next!=null && runner.next.next!=null)
    if runner.next is null, this loop will end and return false.


  • 3
    G

    The first check ( if(head==null) return false; ) is unnecessary: the rest of the code handles it.


  • 6

    You can make use of Floyd's cycle-finding algorithm, also know as tortoise and hare algorithm. The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes. If the linked list has a loop they will definitely meet.


  • 0
    E

    brilliant!!!


  • 21
    D

    @Da_Zhen Since the runner's speed is faster than walker, then it is guaranteed that runner will pass walker in some time. The only thing we need to prove is that the runner never jumps over walker so never meet. Suppose the runner jumps over walker in one unit of time, then we need to guarantee that 2 > distance + 1. So distance < 1 so distance = 0. This implies that runner already meets walker, contradiction. So runner will never jumps over walker.

    Runner will pass walker + runner never jumps over = runner will meet walker.


  • 0
    L

    I tried your code a little differently but did not work.
    I tried this instead :

    while(walker.next != null && runner.next.next != null)
    

    Any ideas why this does not work. I could not figure out why.

    I also tried this instead and did not work:

    while(runner.next.next !=null && runner.next != null)
    

    what is going on?? help !!


  • 4
    D

    @liewsanmin there is a reason why we use runner.next != null && runner.next.next != null. We need to make sure that the runner can really move two steps. If runner can move two steps, walker can move one step.

    You code is likely to suffer null pointer exception because before you use runner.next.next, you didn't check whether runner.next is null or not.


  • 4
    A

    @liewsanmin while(walker.next != null && runner.next.next != null) I think you can imagin one situation that runner.next=null, in this case walker.next!=null satisfiers since it is much slower than runner,and runner.next.next has no definition since runner.next=null.So i think the system will not let you go through.
    while(runner.next.next != null && runner.next!= null) I think the reason is the same as the second reason mentioned above.


  • 1

    @dachuan.huang No, i don't think this code will have null pointer exception or segfault. Because runner.next != null && runner.next.next != nulalready checks runner.next before checking runner.next.next. If runner.next is null, then the statement after "&&" will not be checked.


  • 0

    @marriema said in O(1) Space Solution:

    @dachuan.huang No, i don't think this code will have null pointer exception or segfault. Because runner.next != null && runner.next.next != nulalready checks runner.next before checking runner.next.next. If runner.next is null, then the statement after "&&" will not be checked.

    Correct :)


  • 0
    Q

    @fabrizio3 I thought if a linked list has a cycle, there should be no tail?


  • 5

    @queenafly

    Correct, if there is a cycle you won't reach the end of the list, it would be like this:

    alt text


  • 0
    Q

    @fabrizio3 right. Thanks for your reply! I originally thought if there is no tail, then no node has next pointer pointing to NULL. But here the logic is that if a cycle exists, there will be no tail, and eventually it will jump out of the loop; if not, there will be a tail and the condition in While() still valid.


  • 2
    I

    @gastonbm it's necessary, because runner.next will throw an exception.


  • 0
    A

    @fabrizio3 I have basically the same idea, but why is my code (more specifically the while loop) not working? what edge case am I missing?

    public boolean hasCycle(ListNode head) {
        if (head==null) return false;
        ListNode slow = head;
        ListNode fast = head;
        while (fast!=null){
            //System.out.println("*");
            if (slow==fast)return true;
            slow = slow.next;
            fast = fast.next.next;
        }
        return false;
    }

Log in to reply
 

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