CODEWITHSUNDEEP
pythonloopsdata-structureslinked-list
Ignoramus Sapien
Ignoramus Sapien

Reputation: 11

Linked List Loop detection basic 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

Upvotes: 0

Views: 61

Answers (2)

Anshul Garg
Anshul Garg

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

PreciseMotion
PreciseMotion

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

Related Questions