The same sample runs out the right answer on my IDE, but wrong on leetcode.


  • 0
    L

    Input: {-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5}, tail connects to node index 24

    Output: tail connects to node index 26

    Expected: tail connects to node index 24

     public class Solution {
    
            private int hit(ListNode slow, ListNode fast) {
                int hit = 0;
                if (fast == null || fast.next == null) {
                    hit = -1;
                } else if (slow == fast || slow == fast.next) {
                    hit = 1;
                }
                return hit;
            }
    
            private ListNode cycleHit(ListNode test, ListNode cycle) {
                //Because there must be a cycle, so there is no need to check if these two args are null.
                ListNode start = cycle;
                ListNode cycling = cycle;
                while (true) {
                    if (test == cycling) {
                        return test;
                    }
                    if (start == cycling) {
                        return null;
                    }
                    cycling = cycling.next;
                }
            }
    
            public ListNode detectCycle(ListNode head) {
                if (head == null) {
                    return null;
                }
                ListNode slow = head;
                ListNode fast = head.next;
                while (true) {
                    int result = hit(slow, fast);
                    if (result < 0) {
                        return null;
                    } else if (result > 0) {
                        break;
                    }
                    slow = slow.next;
                    fast = fast.next.next;
                }
                //So, if the code runs in here, it means that there have to have a cycle.
                ListNode test = head;
                while (true) {
                    ListNode hit = cycleHit(test, slow);
                    if (hit != null) {
                        return hit;
                    }
                    test = test.next;
                }
            }
        }
    

    Thanks!


  • 1
    M

    Right now, you detect the cycle correctly, but then try to find the cycle creates an problem.

        private ListNode cycleHit(ListNode test, ListNode cycle) {
            //Because there must be a cycle, so there is no need to check if these two args are null.
            ListNode start = cycle;
            ListNode cycling = cycle;
            while (true) {
                if (test == cycling) {
                    return test;
                }
                if (start == cycling) {
                    return null;
                }
                cycling = cycling.next;
            }
        }
    

    You start out with start and cycling both equal to cycle, the slow node. Then you compare test against cycling, which often fails, and then start against cycling, which will always succeed the first time, since neither value has been changed since you assigned them as equal values. Therefore, this method will only return the node if test==cycling passes on its first try, which means test must equal cycle.

    Since cycle is the slow node there is no guarantee it is the start of the cycle, as you've found out.

    To fix this, use ListNode cycling = cycle.next; as the assignment instead. This algorithm may be a bit slow as well, though, so you might get TLE when you use it.


  • 0
    L

    Thank you! It works! My bad.


Log in to reply
 

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