CODEWITHSUNDEEP
loopsdata-structureslinked-list
Ashish Anand
Ashish Anand

Reputation: 3581

Detecting loop in a Linked List

How to detect loop in a linked list using only single pointer? (Don't want slow and fast pointers(Hare and Tortoise))

Upvotes: 3

Views: 477

Answers (4)

Yilmaz
Yilmaz

Reputation: 49265

class Solution:
    def hasCycle(self, head: ListNode) -> bool:
        if not head:
            return False
        current_node = head
        seen = set()
        while (current_node not in seen):
            # This means there is a tail
            if current_node.next == None:
                return False
            seen.add(current_node)
            current_node = current_node.next
        # current_node would be the start of the cycle
        return True

Upvotes: 0

false
false

Reputation: 10102

Brent's algorithm is clearly the best here: For loop-free lists it simply visits the list once while Floyd's tortoise and hare requires to revisit half of the nodes. For lists with loops it never "rotates" longer in the loop than Floyd ; and in the best case needs only one cycle, when Floyd needs many. Think of a long loop-free sequence followed by a loop of lenght 1. In this case, the best case for Brent would be to detect the cycle after one visit of the loop - so visiting each node exactly once ; whereas Floyd has to visit each node on average three times.

The basic idea is to visit the linked list and compare the pointer of the current node with one already visited node. That is, one pointer comparison per visited node. The pointer is updated from time-to-time following a simple logic.

Upvotes: 1

Juan Carlos Diaz
Juan Carlos Diaz

Reputation: 1

If your nodes are composed of value and a pointer to next node, you can use the list creating a pointer to the first node. You can check, on every node, if pointer has the same value than pointer to first node.

Upvotes: 0

MAK
MAK

Reputation: 26586

You could use a hastable to store visited nodes as you go forward along the linked list, if you don't mind the extra O(N) memory.

At each node you check whether the node already exists in the hashtable. If it does, you have found a loop. Otherwise you add it to the hashtable and move on to the next node.

Upvotes: 1

Related Questions