Different orders of "fast=fast.next.next; slow=slow.next" may cause TLE? Why


  • 1
    W

    I use following orders to run on OJ, it ends up with Time Limit Exceeded

    test case:

    Last executed input: {7032,15013,6890,8877,11344,320,......,-2218}, tail connects to node index 5902

        public ListNode detectCycle(ListNode head) {
        ListNode fast = head;
        ListNode slow = head;
        
        while(fast != null && fast.next != null) {
            **fast = fast.next.next;
            slow = slow.next;**
            if(fast == slow) break;
        }
        if(fast == null || fast.next == null)
            return null;
        ListNode p = head;
        while(p != slow) {
            slow = slow.next;
            p = p.next;
        }
        return p;
    }
    

    However when use following code, there is no problem. Can someone explain this?

        public ListNode detectCycle(ListNode head) {
       
        ......
        while(fast != null && fast.next != null) {
            **slow = slow.next;
            fast = fast.next.next;**
        }
        ......
    }

  • 0
    D

    I didn't look at your code in detail, but it looks like what I ran into also.

    Assume head is k positions (nodes) from the start of the loop. Then in the first (loop detection) phase, you must wind up with the collision point in the loop also k nodes from the start. If it is not, your p and slow will wind up chasing each other around the loop forever. Different ways of coding the detection phase can leave the in-loop pointer (slow, in your case) off-by-one from where it needs to be for the loop-start-detection phase to work.

    You can see this easily if you can run your code in a debugger.


Log in to reply
 

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