IDE gives me warning EXC_BAD_ACCESS and OJ gives {} 0 cycle run time error.


  • 0
    Y

    My strategy is the dumbest O(n2) way in which I use cursor2 to traverse every node explored by cursor1. But it is the first time I make it by myself without external assistance.

    I made three test drivers, root, roo2, and root0. Weird though, my IDE(xcode) runs well when I test on root0 only, but reports thread problem with EXC_BAD_ACCESS when running all three together. root and root2 works fine as well.

    Hi, it looks like my code is having problem in the case of null linked list. But I think I have taken care of it. As I have use if condition before the while loop.

    Can anyone give a hint of what happens? Thanks!

     /**
         * Definition for singly-linked list.
         * struct ListNode {
         *     int val;
         *     ListNode *next;
         *     ListNode(int x) : val(x), next(NULL) {}
         * };
         */
        
        #include<iostream>
        using namespace std;
        
        struct ListNode{
            int val;
            ListNode *next;
            //ListNode(int x) : val(x), next(NULL) {}
        };
        
        class Solution
        {
        public:
            bool hasCycle(ListNode *head)
            {
                ListNode * cursor1;
                ListNode * cursor2;
                
                int counter = 0;
                
                if (!head || !head->next)
                {
                    return false;
                }
                else
                {
                    cursor1 = head;
                    while (cursor1->next)
                    {
                        cursor1 = cursor1->next;
                        counter++;
                    
                        cursor2 = head;
                        for (int i=0;i<counter;i++)
                        {
                            if(cursor1 == cursor2)
                            {
                                return true;
                            }
                            cursor2 = cursor2->next;
                        }
                    }
                }
                return false;
            }
        };
        
        int main()
        {
            //test1: with cycle;
            
            ListNode *root;
            root = new ListNode;
            root->val = 0;
            
            root->next = new ListNode;
            root->next->val = 1;
            
            root->next->next = new ListNode;
            root->next->next->val= 2;
            
            root->next->next->next = new ListNode;
            root->next->next->next->val = 3;
            
            root->next->next->next->next = new ListNode;
            root->next->next->next->next->val = 4;
            
            root->next->next->next->next->next = root->next;
            
            //test2: without cycle
            
            ListNode *root2;
            root2 = new ListNode;
            root2->val = 0;
            
            root2->next = new ListNode;
            root2->next->val = 1;
            
            root2->next->next = new ListNode;
            root2->next->next->val= 2;
        
            root2->next->next->next = new ListNode;
            root2->next->next->next->val = 3;
            
            root2->next->next->next->next = new ListNode;
            root2->next->next->next->next->val = 4;
            
            //test3: null list
            
            ListNode *root0;
            //root0 = new ListNode;
            
            Solution test;
            cout << test.hasCycle(root) << endl;
            cout << test.hasCycle(root2) << endl;
            cout << test.hasCycle(root0) << endl;
            
            return 0;
            
        }

Log in to reply
 

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