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;
}

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. — slim
– slim, Commented Jul 7, 2017 at 13:12
For the simple cases it looks not wrong. Test data would be good. — Fischer Ludrian
– Fischer Ludrian, Commented Jul 7, 2017 at 13:13
@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". — Florent Bayle
– Florent Bayle, Commented Jul 7, 2017 at 13:26

RoflcoptrException · Accepted Answer · 2017-07-07 13:29:28Z

4

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.

answered Jul 7, 2017 at 13:29

RoflcoptrException

52.3k35 gold badges154 silver badges200 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

slim Over a year ago

Or use a HashSet and don't bother with the value.

RoflcoptrException Over a year ago

Sure, but as the OP has already said, they wanted to implement it using HashMap because it already works with a HashSet.

slim Over a year ago

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...

Klitos Kyriacou · Accepted Answer · 2017-07-07 13:29:14Z

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.

answered Jul 7, 2017 at 13:29

Klitos Kyriacou

11.9k3 gold badges50 silver badges86 bronze badges

Comments

Austin_Anderson · Accepted Answer · 2017-07-07 13:32:17Z

0

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;
}

answered Jul 7, 2017 at 13:32

Austin_Anderson

9507 silver badges17 bronze badges

1 Comment

Klitos Kyriacou Over a year ago

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.

Collectives™ on Stack Overflow

finding loop in linked list using HashMap in java

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

3 Comments

Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related