3
\$\begingroup\$

I'm solving HackerRank "Linked Lists: Detect a Cycle" challenge.

A linked list is said to contain a cycle if any node is visited more than once while traversing the list.

Complete the function provided in the editor below. It has one parameter: a pointer to a Node object named head that points to the head of a linked list. Your function must return a boolean denoting whether or not there is a cycle in the list. If there is a cycle, return true; otherwise, return false.

Note: If the list is empty, head will be null.

/*
Detect a cycle in a linked list. Note that the head pointer may be 'null' if the list is empty.

A Node is defined as: 
    class Node {
        int data;
        Node next;
    }
*/

boolean hasCycle(Node head) {
    HashSet<Node> seen = new HashSet<Node>();

    Node current = head;
    while (current != null && current.next != null) {
        if (seen.contains(current)) {
            return true;
        }

        seen.add(current);
        current = current.next;
    }

    return false;
}

As a beginner Java developer, what can be improved here?

\$\endgroup\$
  • \$\begingroup\$ 200_success already suggested nice improvements, and this solution is perfectly fine, but you might want to be aware that there is another algorithm that doesn't use additional memory: stackoverflow.com/a/2663147/1550964 \$\endgroup\$ – Duarte Meneses Nov 15 '17 at 15:40
  • \$\begingroup\$ I am not sure if you want spoilers, but I think you can get a better complexity than using this algorithm when you know the maximum number of elements in the list (which is given in the hackerrank task). This information can help a lot. If you do not know the (max) number of elements your algorithm is fine. \$\endgroup\$ – allo Nov 15 '17 at 15:43
3
\$\begingroup\$

The method should be public.

Testing for the current.next != null condition is unnecessary. Also, consider writing the loop as a for loop for clarity:

for (Node current = head; current != null; current = current.next) {
    …
}

You don't need to call seen.contains(), because seen.add() will return false if the item you are adding is already in the set.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.