Given the head of a Singly Linked List that contains a loop, which is the list's tail points to some node in the list instead of none.
Given a standard class of Linked List
class LinkedList:
def __init__(self, value):
self.value = value
self.next = None
When we look through the Linked List we should return where the loop returns us too. So after our tail node, we return what comes after that.
We look at 2 nodes at a time moving at different speeds. If the nodes ever equal each other, then that is where our loop is.
def findLoop(head):
first = head.next
second = head.next.next
while first != second:
first = first.second
second = second.next.next
while first != second:
first = first.next
second = second.next
return first
Top comments (0)