Get TLE: "Last executed input: {1,2}, tail connects to node index 0", anyone can help me?


  • 0
    A

    My Code:

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

    It showed " Time Limit Exceeded
    Last executed input: {1,2}, tail connects to node index 0"

    I'm quite confused about it. Anyone can help me? Thank you.


  • 0
    R

    I will help you. Take a look of my answer.


  • 3
    R
      public class Solution {
            public ListNode detectCycle(ListNode head) {
                if(head == null || head.next == null){
                    return null;
                }
                ListNode slow = head;
                ListNode fast = head;
                while(fast != null) {// Do not use OR in the loop condition, your second argument is actually uselss
                    slow = slow.next;
                    fast = fast.next;//Here your code is fast=slow.next.next. So it gets TLE
                    if(fast!=null) fast=fast.next;
                    if (fast==slow) break;//Make sure fast always runs 2X faster than slow
                }
                if(fast == null )
                    return null;
                
                slow = head;
                while(slow != fast){
                    fast = fast.next;
                    slow = slow.next;
                }
                return fast;
            }
        }

  • 0
    A

    Thank you so much~


  • 0
    R

    Why not choose my answer as the best one?


  • 0
    A

    Done. Just learning how to use this question system.


Log in to reply
 

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