Reputation: 11
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
Upvotes: 0
Views: 61
Reputation: 11
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
Upvotes: 0
Reputation: 350
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.
Upvotes: 1