Shorter Solution in Java


  • 23
    P
    class HasCycleInLinkedList{
       public boolean hasCycle(ListNode head){
           if(head == null || head.next == null) return false;
           if(head.next == head) return true;
           ListNode nextNode = head.next; 
           head.next = head;
           boolean isCycle = hasCycle(nextNode);
           return isCycle;
       }
    }

  • 0
    S

    Your solution is greate! I think it's wonderful


  • 0
    H

    can you give some insight for the recursion solution? The end result seems only cover 2 nodes loop. How about those big loop?


  • 4
    M

    The program gives every visited node a sign by pointing next to the node itself.


  • 1
    H

    You mean this line: head.next = head;
    got it!
    If the linkedList has cycle, the recursion will continue to revisit the signed node who has visited before. Should the problem has check to stop the recursion when isCycle become true?


  • 0
    M

    if(head.next == head) return true;
    This is the check line.


  • 2
    Y

    This solution breaks the original linked list structure. Is it OK?


  • 0
    A

    Nice recursive solution.


  • 0
    Z

    Anyway, the solution shouldn't break original links.


  • 0
    A

    If modifying the linked list is OK then it can done even shorter:

    public boolean hasCycle(ListNode head) {
        while( head != null ) {
            if( head.val == 0xcafebabe ) return true;
            head.val = 0xcafebabe; // Mark this node as visited
            head = head.next;
        }
        return false;
    }
    

    even more shorter:

    public boolean hasCycle(ListNode head) {
        if ( head == null ) return false;
        if( head.val == 0xcafebabe ) return true;
        head.val = 0xcafebabe; // Mark this node as visited
        return hasCycle(head.next);
    }

  • 1

    Even shorter:

    public boolean hasCycle(ListNode head) {
        return head!=null && (head.val == (head.val = 0xcafebabe) || hasCycle(head.next));
    }
    

    Although we're just lucky that LeetCode apparently doesn't like cafe babes. The OP's solution doesn't have such a problem.


  • 0
    M

    Note that "head.next = head". This makes node.next point to itself. That is, each node that we have visited points to itself. So if there exist a loop, we will finally visit a node that points to itself.


  • 0
    M

    I'm wondering whether we could change the original list structure.


Log in to reply
 

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