Run Time error for large input


  • 0
    K

    Hi,

    I'm trying to the solve the cycle in a linked list problem. I'm getting a Run-time error on a very large input which I cannot paste( its too long). I'm not sure, if my code is buggy. Any help appreciated :)

    Algorithm:

    1.The usual fast, slow pointer algorithm

    1. Then find length of loop "r"

    2. Move a pointer "p" to "r" places from the start

    3. Now start from head with another pointer "q" and move p and q simultaneously until they meet.

      /**

      • Definition for singly-linked list.

      • class ListNode {

      • int val;
        
      • ListNode next;
        
      • ListNode(int x) {
        
      •     val = x;
        
      •     next = null;
        
      • }
        
      • }
        */
        public class Solution {
        public ListNode detectCycle(ListNode head) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        System.out.println("caught up");

         if(head == null)
             return null;
         
         ListNode slow = head;
         ListNode fast = head;
         do {
             if(fast.next == null) 
                 return null;
             else {
                 slow = slow.next;
                 fast = fast.next.next;
             }
             
         }while( (fast != slow) && (fast != null));
         
         System.out.println("caught up");
         
         int loop_length=0;
         
         do {
             slow = slow.next;
             loop_length++;
         }while(slow != fast);
         
         ListNode front = head;
         ListNode back = head;
         
         while(loop_length > 0) {
             front = front.next;
             loop_length--;
         }
         
         while(back != front) {
             back = back.next;
             front = front.next;
         }
         
         return back;
        

        }
        }


  • 6
    C

    Here is my solution. You make thing complicated. When slow==fast, you just need let slow=head, then move slow and fast point forward. And they will meet at the begin of cycle.

    class Solution {
    public:
        ListNode *detectCycle(ListNode *head) {
            if(!head) return NULL;
            ListNode *fast = head->next;
            ListNode *slow = head;
            while(fast && fast->next){
                if(slow == fast){
                    slow = head;
                    fast = fast->next;
                    break;
                }
                fast = fast->next->next;
                slow = slow->next;
            }
            if(!fast || !fast->next) return NULL;
            while(slow != fast){
                fast = fast->next;
                slow = slow->next;
            }
            return fast;
        }
    };

Log in to reply
 

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