Detecting a cycle in a linked list using Java

Question

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?

• Duarte Meneses: 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
• allo: 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.

Answer 1

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.