Linked List Loop detection basic question

Question

So this is my code to detect loop. I have a doubt here. Why am I looking for current in dic instead of current.data in dic.? Its giving wrong answer if I store that value of the node alone. What happens when I store the value of the node instead of the Node. I am learning linked list, SO I am unable to grasp what happens when I store the Node itself and what happens when I store the value of Node alone.

def detectLoop(head):

    dic={}
    current=head
    flag=5
    while current is not None:
        if current in dic:
            flag=6
            break
        else:
            dic[current]=5
            current=current.next
    if flag==5:
        return False
    else:
        return True

Multiple nodes may have the same value, in this case storing and comparing all values from visited nodes would give false positives — Iain Shelvington
– Iain Shelvington, Commented Aug 26, 2019 at 4:23
Yes Sir. Thats right. But what happens when I store the node? Like how does it detect that its the same node? — Ignoramus Sapien
– Ignoramus Sapien, Commented Aug 26, 2019 at 4:24

PreciseMotion · Accepted Answer · 2019-08-26 04:24:00Z

1

By comparing the node, you are checking if you are running across the same node object twice. By checking the value you are ignoring the situation where two nodes may share the same value, and thus, your method would report that there is a cycle when there really isn't. If there were no nodes with duplicate values, it wouldn't matter.

answered Aug 26, 2019 at 4:24

PreciseMotion

3501 silver badge14 bronze badges

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

7 Comments

Ignoramus Sapien Over a year ago

Sir, That's my doubt. How come it identifies that its the same node object? Whats happening internally?

Ignoramus Sapien Over a year ago

Yes Sir. I understood that. One more doubt.

Ignoramus Sapien Over a year ago

When I declare, Self.head.next=Node(z), What I am telling is the next node of the head has the value of z?

Ignoramus Sapien Over a year ago

And self.head.next is a separate node right now. right sir? Did I get it right?

Ignoramus Sapien Over a year ago

Thank you Sir. Finally understood it. :)))

|

Anshul Garg · Accepted Answer · 2019-08-26 06:22:10Z

0

If one has to detect the loop in the linked-list there is an easier and space-efficient method of 2 pointers Take two references or pointers(fast and slow). 'fast' moves a pace of two, every time 'slow' moves one; like fast = fast->next->next and slow = slow->next. In case both of them at any point meet again then there is a loop in the linked-list

answered Aug 26, 2019 at 6:22

Anshul Garg

114 bronze badges

Collectives™ on Stack Overflow

Linked List Loop detection basic question

2 Answers 2

7 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

7 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related