Why TLE, {3,2,0,-4}, tail connects to node index 1


  • 0
    L

    Why the input like {3,2,0,-4} resulted in TLE? The algorithm is pretty like others: 1) first loop to find out whether there is a cycle. 2) reset p to head and another loop to find the beginning of the cycle...

    And for {3, 2, 0,-4}, only first iteration is mandatory.

    public class Solution
    {
    	public ListNode detectCycle(ListNode head) 
    	{
    		if (head == null || head.next == null)
    			return null;
    
    		ListNode p = head;	
    		ListNode q = head.next.next;
    		
    		while (p != null && q!= null)
    		{
    			if ( p == q)
    				break;
    			
    			p = p.next;
    			q = q.next;
    			if (q != null)
    				q = q.next;
    		}
    
    		if (p == null || q == null)
    			return null;
    		
    		// must have a cycle
    		p = head;
    		while (p != q )
    		{			
    			p = p.next;
    			q = q.next;
    		}
    		
    		return p;
    	}
    }

  • 0
    D

    problem is in code section

    // must have a cycle

        p = head;
        while (p != q )
        {           
            p = p.next;
            q = q.next;
        }
    

    you can refer to this link..
    http://www.geeksforgeeks.org/detect-and-remove-loop-in-a-linked-list/


  • 0
    L

    {3, 2, 0,-4} won't go to this part since there is no loop. it returns at

            if (p == null || q == null)
                return null;
    

  • 0
    L

    I think online judge has the bug. My original solution should work out. The following was accepted. The biggest change is not to initialize the fast to head.next.next.

    public ListNode detectCycle(ListNode head)
    {
    	if (head == null || head.next == null)
    		return null;
    
    	ListNode slow = head;
    	ListNode fast = head;
    
    	while (slow != null && fast != null)
    	{			
    		slow = slow.next;
    		fast = fast.next;
    		if (fast != null)
    			fast = fast.next;
    		
    		if (slow == fast )
    			break;
    	}
    
    	if (slow == null || fast == null)
    		return null;
    	
    	// must have a cycle 
    	slow = head;
    	while (slow != fast)
    	{
    		slow = slow.next;
    		fast = fast.next;
    	}
    
    	return slow;
    }
    

    }


  • 0
    L

    see my updated codes. This code snippet worked out.


Log in to reply
 

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