Time limit ! Please help


  • 0
    A

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


  • 0
    S

    The way you drafted your code is not very readable. Let me first try to reconstruct your code in right format. Let me know if I got it wrong.

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

    If the above is right, then if I understand it correct, you are trying to traverse the list with the "fast" pointer (I'm not sure why you named it like that :)). At every pointer advance, you are making the previous node to point itself. This is something like marking a node as visited. And then if at all the list has a cycle then the traversal will reach the node whose pointer has already been changed (I refer to as visited) and then we can return the pointer to that node. Clever !! But what the issue here could be is the fact that in this process you destroyed the original list and the test cases might be trying to look for it. Try updating the code to reconstruct the list and resubmit to see the difference.


  • 0
    S

    Good to know you liked the answer. Thank you for voting it as best answer.


Log in to reply
 

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