0

I am doing some HankerRank challenges to practice algorithms/data structures, and I am having trouble. The problem is to detect loops in a singly linked list. This is an obvious use of Floyd's cycle finding algorithm, but I can't seem to get it to work. I also checked my answer to others, and it seems to be doing the same thing. If anyone can help me out I would appreciate it. 

 // Complete the hasCycle function below.

    /*
     * For your reference:
     *
     * SinglyLinkedListNode {
     *     int data;
     *     SinglyLinkedListNode next;
     * }
     *
     */
    static boolean hasCycle(SinglyLinkedListNode head) {

        // https://stackoverflow.com/questions/2663115/how-to-detect-a-loop-in-a-linked-list

        SinglyLinkedListNode start = head;

        //there is no list
        if(start == null) { 
            return false;
        }

        // have both start at beginning
        SinglyLinkedListNode slow = head;
        SinglyLinkedListNode fast = head;

        while(true) {

            slow = slow.next; //hop one ahead

            //fast.next may be null, so fast.next.next will cause a null pointer exception
            if(fast.next != null) {
                fast = fast.next.next; //hop two ahead
            } else {
                return false;
            }

            //They are the same node so 'slow' must have caught up
            if(slow == fast) {
                return true;
            }

            //We reached the end of the list with no next, so there must not be a loop
            if(slow == null || fast == null) {
                return false;
            }

        }

    }

Thanks for any advice.

****EDIT**** Sorry for being unclear about what the problem is. When running it on HackerRank, the following input: 1 1 3 1 2 3, fails. My code returns that there is no cycle, when the correct answer is that there is a cycle.

Logan Phillips
  • 660
  • 2
  • 10
  • 23
  • 1
    What errors are you getting? – Sam Jul 17 '18 at 15:11
  • 1
    "I can't seem to get it to work" What is the actual problem? Runtime exception? Infinite loop? Incorrect results? Questions seeking debugging help must include a specific problem or error, else they are off-topic. – Michael Jul 17 '18 at 15:11
  • In what case does it fail? – Johannes Kuhn Jul 17 '18 at 15:13
  • 1
    Is there a reason you moved `slow == fast` to happen before `slow == null || fast == null`? – Michael Jul 17 '18 at 15:16
  • @Michael Sorry, I updated it. And there is no particular reason. I just thought about slow == fast before the other check. I didn't think it mattered which one was first. – Logan Phillips Jul 17 '18 at 15:28
  • Are you sure you construct the list correctly? – user58697 Jul 17 '18 at 17:13
  • @user58697 Yes, this is a problem off of HankerRank. – Logan Phillips Jul 17 '18 at 18:05
  • In case I was not clear: The loop detection part is correct. It means that the problem is elsewhere, in the part of code you did not show. Most likely, it is in the list construction. – user58697 Jul 17 '18 at 18:41
  • @user58697 I'll have to look more closely. There is code that constructs the list for you, so I doubt there could be a problem there. – Logan Phillips Jul 19 '18 at 13:09
  • @LoganPhillips when you initialize `slow` and `fast`, fast always needs to be 2 nodes ahead of `slow`. So, `fast = head.next.next`. – nice_dev Jul 28 '18 at 04:57

0 Answers0