finding loop in linked list using HashMap in java

Question

i am writing code for lop detection in linked list using hashmap. why it goes in infinite loop?

boolean hasCycle(Node head) {
 HashMap<Integer,Node> map = new HashMap<Integer,Node>();
 //<Address,data>
 if(head == null || head.next == null)
 return false;
 Node p = head;
 while(p.next!=null)
 {
 if(map.containsValue(p.next))
 {
 return true;
 }
 else
 {
 map.put(p.data,p.next);
 }
 p = p.next;
 }
 return false;
}

• Florent Bayle: Why are you using a HashMap instead of a HashSet ?
• Teekam: Can you provide test data
• slim: ericlippert.com/2014/03/05/how-to-debug-small-programs -- explain to a duck why it should not loop infinitely. If that doesn't help, use a debugger and step through it. When it does something you didn't expect, you've found the problem.
• Fischer Ludrian: For the simple cases it looks not wrong. Test data would be good.
• Florent Bayle: @parimal You will have to provide a Minimal, Complete, and Verifiable example if you want us to be able to help you, othervise your question will be closed as being "a problem that can no longer be reproduced".

Answer 1

Use the Node as key and the data field as value and then check whether the HashMap contains the key:

boolean hasCycle(Node head) {
 HashMap<Node,Integer> map = new HashMap<Node,Integer>();
 if(head == null || head.next == null)
 return false;
 Node p = head;
 while(p.next!=null) {
 if (map.containsKey(p.next)) {
 return true;
 } else {
 map.put(p.next,p.data);
 }
 p = p.next;
 }
 return false;
}

And also follow the Java Code Conventions.

• slim: Or use a HashSet and don't bother with the value.
• RoflcoptrException: Sure, but as the OP has already said, they wanted to implement it using HashMap because it already works with a HashSet.
• slim: Ah, that comment is new. Presumably, then, OP wants to use a HashMap<Value,Node> for some other purpose (perhaps making the algorithm check for cycles and do other work in the same pass), which means a HashMap<Node, Value> is no use either. I suspect it's misguided anyway...

Answer 2

Your code calls

map.containsValue(p.next)

This method iterates through the whole map looking for an object that is equal to the passed argument. To do that, it calls your Node.equals() method. It is highly probable that this is where it's going into an infinite loop.

To solve it, you could just use a HashSet of the Node objects (as mentioned in the comments) and check that your equals() and hashCode() methods are correct. But there is also another way to check for cycles, which doesn't involve the use of any extra memory. You just use two iterators, one going at half the speed of the other. If there is a cycle, the faster iterator will lap the slower one.

Answer 3

Have you defined .equals() and .hashCode() on your Node class? if not, it defaults to ==, and if the HashMap makes a copy of your Node as it inserts or moves it in memory, and then your equivalence would fail, because == compares memory addresses.

assuming your node class is akin to

public class Node{
 public int data;
 public Node next;
}

you could define them as

@Override
public int hashCode(){
 int nextData=next.data;
 return data^nextData;
}
@Override
public boolean equals(Object other){
 boolean equal=false;
 if(other!=null&&other instanceof Node){
 Node otherNode=(Node)other;
 if(otherNode.data==data){
 if(otherNode.next==null&&next==null){
 equal=true;
 }else if(otherNode.next!=null&&next!=null){
 if(otherNode.next.data==next.data){ 
 equal=true;
 }
 }
 }
 }
 return equal;
}

• Klitos Kyriacou: Java's HashMap doesn't clone any of the object it contains; when it expands, it simply copies references to the same objects. Therefore, if the OP had left hashCode() and equal() undefined, the hasCycle() method would have worked. I think they were defined, but incorrectly.