How to detect loop in a linked list using only single pointer? (Don't want slow and fast pointers(Hare and Tortoise))
3
-
It would already have been a pretty artificial question if the answer had been the hare and tortoise algorithm.Pascal Cuoq– Pascal Cuoq2011-10-09 18:54:31 +00:00Commented Oct 9, 2011 at 18:54
-
What do you mean by "using only single pointer?" You already use one pointer storing a pointer to the head of the list; are you allowed to make any pointers other than that?templatetypedef– templatetypedef2013-01-07 02:12:14 +00:00Commented Jan 7, 2013 at 2:12
-
@templatetypedef: two pointers can only mean here: two pointers visiting the linked list.false– false2013-01-07 03:34:28 +00:00Commented Jan 7, 2013 at 3:34
Add a comment
|
4 Answers
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.
2 Comments
templatetypedef
But doesn't this require multiple pointers (one for each node stored in the hash table?)
MAK
@templatetypedef: True. I read "using a single pointer" as meaning using a single pointer to iterate over the list as opposed to using two pointers. This uses a single pointer for the iteration, but we are still storing pointers to all the nodes visited - hence the O(n) memory which I mentioned in my answer. I figured the OP may be fine with that.
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.
1 Comment
false
@templatetypedef: Only one pointer sifts through the linked list. The other is set to the value of the first from time to time.
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.
1 Comment
templatetypedef
What if the cycle spun back into the middle of the list, not the front?
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
