DEV Community

loading...

Finding a Loop in a Singly Linked List in Python

jabermudez11 profile image Justin Bermudez ・1 min read

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Discussion

pic
Editor guide