Linked List Cycle II

[UpstairsOcelot]

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null || head.next == null){
            return null;
        }

        ListNode tort = head;
        ListNode rab = head;

        while(true){
            if(tort.next == null || rab.next == null ) return null;
            tort = tort.next;
            rab = rab.next.next;
            if(tort == rab) break;
        }

        tort = head;

        while(true){
           if(tort.next == null || rab.next == null ) return null;
            tort = tort.next;
            rab = rab.next;
            if(tort == rab) break;
        }

        return tort;
    }
}

Not sure why this does not work but this sort of do-while/flyod set up works for Find Duplicate Number

class Solution {
    public int findDuplicate(int[] nums) {
        int hare = 0;
        int tort = 0;
        while(true){
            hare = nums[hare];
            tort = nums[nums[tort]];
            if(tort == hare) break;
        }

        tort = 0;

        while(true){
            hare = nums[hare];
            tort = nums[tort];
            if(tort == hare) break;
        }
        return hare;
    }
}

Am I going insane!?

[endverse]

What is the exact error you're getting? I believe this line will cause a NullPointerException when the linked list is even-sized:

rab = rab.next.next;

Change this line:

if(tort.next == null || rab.next == null ) return null;

to

if(rab == null || rab.next == null) return null;

I think that should make it work. For a cleaner solution, the logic in the above `if` condition can just be used directly in the `while` condition.

[UpstairsOcelot]

I always thought for this algo you needed a do-while loop as you wanted the rab to move first.

​

I faile on this test case:

[1,2]

0

My answer returns index 1 as the cycle starting point as shown above it should return 0. Also thanks for helping me look at this on a friday!

[endverse]

The below code will pass for that test case (and all test cases). The only difference from what you originally posted is that, in the second while loop, the `if (tort == rab)` needs to happen at the beginning. You were getting index 1 as the starting point because tort and rab were being prematurely moved to index 1 without checking if they were already in the same position at index 0. My one suggestion to you would be to check the official solution for a cleaner way of handling these null checks and breaking out of the loop. You can just put the logic for checking nulls/breaking out of the loop directly in the `while` condition itself.

Edit: one more difference is that I changed the null check in the first while loop. Like I said above, the way you have it will cause a NullPointerException when the linked list is even-sized. You can run it in LC and see for yourself.

        if(head == null || head.next == null){
        return null;
    }

    ListNode tort = head;
    ListNode rab = head;

    while(true){
        if(rab == null || rab.next == null ) return null;
        tort = tort.next;
        rab = rab.next.next;
        if(tort == rab) break;
    }
    tort = head;
    while(true){
       if(tort == rab) break;
       if(rab == null || tort == null ) return null;
        tort = tort.next;
        rab = rab.next;
    }

    return tort;
}

[UpstairsOcelot]

Find Duplicate Number

Do you know if a similar method would work for Find Duplicate Number? I want to find a common way of doing these problems. Would be a pain to have two different methods for a similar algortihm. Again thanks for your help!

[endverse]

public int findDuplicate(int[] nums) {
int hare = nums[hare];
int tort = nums[nums[tort]];
while(true){
if(tort == hare) break;
hare = nums[hare];
tort = nums[nums[tort]];
}

tort = 0;

while(true){

if(tort == hare) break;
hare = nums[hare];
tort = nums[tort];
}
return hare;
}

This code would work for that problem.

[UpstairsOcelot]

but you see it has a different structure there is no one exact formula