3

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

asked Oct 9, 2011 at 18:49
3
  • It would already have been a pretty artificial question if the answer had been the hare and tortoise algorithm. Commented 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? Commented Jan 7, 2013 at 2:12
  • @templatetypedef: two pointers can only mean here: two pointers visiting the linked list. Commented Jan 7, 2013 at 3:34

4 Answers 4

1

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.

answered Oct 9, 2011 at 19:06
2
  • But doesn't this require multiple pointers (one for each node stored in the hash table?) Commented Jan 7, 2013 at 2:11
  • @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. Commented Jan 7, 2013 at 9:12
1

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.

answered Jan 7, 2013 at 0:53
1
  • @templatetypedef: Only one pointer sifts through the linked list. The other is set to the value of the first from time to time. Commented Jan 7, 2013 at 3:23
0

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.

answered Oct 9, 2011 at 19:11
1
  • 1
    What if the cycle spun back into the middle of the list, not the front? Commented Jan 7, 2013 at 2:11
0
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
answered Nov 3, 2021 at 0:14

Your Answer

Draft saved
Draft discarded

Sign up or log in

Sign up using Google
Sign up using Email and Password

Post as a guest

Required, but never shown

Post as a guest

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.