Space O(1) and time O(3n) solution, works well in my pc, but TLE here, can anyone help?


  • 0
    M

    Last executed input: {-1,-7,7,-4,19,6,-9,-5,-2,-5}, tail connects to
    node index 9

    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
        
    	//Check for particular cases
    	
    	    if (head == NULL) return NULL;
            if (head->next == NULL) return NULL;
    	
    	//Travel one
            
            ListNode *head_next = head->next;
        	ListNode *Current = head;
    		ListNode *Before = NULL;
    		ListNode *_Before = NULL;
            while (Current->next!=NULL)
    		{
    			Current->val=0;
    			Before = Current;
    			Current = Current->next;
    			Before->next = _Before;
    			_Before = Before;
    		}
    		
    		if (Current != head)
    			return NULL;
    			
      	//Travel two		
    		_Before = NULL;
            Current->next = head_next;
    		while (Current->next!=NULL)
    		{
    			Current->val++;
    			Before = Current;
    			Current = Current->next;
    			Before->next = _Before;
    			_Before = Before;
    		}
    		
    	//Travel three
    		_Before = NULL;
            Current->next = head_next;
    		while (Current->next!=NULL)
    		{
    			if (Current->next->val==1)
    				return Current;
    			Current = Current->next;
    		}
    	
        }
    };

Log in to reply
 

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