Cycle Detection

Sort by

recency

|

35 Discussions

|

  • + 0 comments

    Java 8

        static boolean hasCycle(SinglyLinkedListNode head) {
            Set<SinglyLinkedListNode> nodeSet = new HashSet<>();
            SinglyLinkedListNode node = head;
            while (node != null) {
                if (nodeSet.contains(node)) {
                    return true;
                }
                nodeSet.add(node);
                node = node.next;
            }
            return false;
        }
    
  • + 0 comments

    This question does have bugs in some languages, such as JavaScript. I ran the following which is exactly equivalent to the working Python 3 solution already posted. That solution passes in Python, but it does not pass in JavaScrpt.

    function hasCycle(head) { let node = head; const visited = {}; while (node) { if (visited[node]) return true; visited[node] = true; node = node.next; } return false; }

  • + 0 comments

    again this question is bugged... the example of the cycle:

    1 -> 2 -> 3 -> 1 -> NULL
    

    1 can't point to both 1 and NULL!

    At least this time the ro class compiles!

    static bool hasCycle(SinglyLinkedListNode head) {
        var d = new HashSet<SinglyLinkedListNode>();
        while(head is not null){
            if(d.Contains(head)) return true;
            d.Add(head);
            head = head.next;
        }
        return false;
    }
    
  • + 0 comments

    Only python works for me...

    Floyd cycle approach

    def has_cycle(head):
        slow = head
        fast = head
        
        while fast is not None and fast.next is not None:
            slow = slow.next
            fast = fast.next.next
            
            if (slow == fast):
                return 1
        
        return 0
    
  • + 1 comment

    static boolean hasCycle(SinglyLinkedListNode head) { if (head == null || head.next == null) { return false; } SinglyLinkedListNode slow = head; SinglyLinkedListNode fast = head.next; while (fast != null && fast.next != null) { if (slow == fast) { return true; } slow = slow.next; fast = fast.next.next; } return false; }