Given a linked list, determine if it has a cycle in it.


  • 0
    Z

    Who can point out the bugs for me? I would really appreciate your help.

    Input: {-21,10,17,8,4,26,5,35,33,-7,-16,27,-12,6,29,-12,5,9,20,14,14,2,13,-24,21,23,-21,5}, no cycle
    Output: true
    Expected: false

    Below is my code:

    public class Solution {
        public boolean hasCycle(ListNode head) {
            ListNode first = new ListNode(0);
            ListNode second = new ListNode(0);
            first = head;
            second = head;
            if(head == null){
                return false;
            }
            if(head.next == null){
                return false;
            }
            while(first != second && second.next.next != null && second.next != null){
                first = first.next;
                second = second.next.next;
            }
           
            if(second.next.next == null || second.next == null){
                return false;
            }
            else return true;
        }
    }

  • 1
    L

    A few comments about the code.

    1). You don't need to allocate new objects for the "first" and "second" pointers in your function. You just need to assign the reference value of "head" to them.
    e.g.

    ListNode first = head, second = head;
    

    2). The first condition in your while loop should be checked inside the loop. Otherwise, for any non-empty and non-single-element list, your function will always return false. The reason is listed in comment 1).
    This is actually the main reason why your solution does not work.

    3). Once you remove the condition in comment 2). You might want to change the order of the rest of the conditions.
    i.e.

    second.next != null && second.next.next != null
    

    Otherwise, NullPointerException.

    Voila.


  • 0
    Z

    Thank you for your solutions. It is fantastic. I have another couple of problems that I cant make run. I will post them later. Thanks again.


Log in to reply
 

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