4

Could someone please let me know the best way to prove a linked list contains a loop? I am using an algorithm with two pointer, one is moving slow with one steps and one is moving faster with two steps.

class Node(object):
    def __init__(self, value, next=None):
        self.next=next
        self.value=value
def create_list():
    last = Node(8)
    head = Node(7, last)
    head = Node(6, head)
    head = Node(5, head)
    head = Node(4, head)
    head = Node(3, head)
    head = Node(2, head)
    head = Node(1, head)
    last.next = head
    return head

def is_circular(head):
    slow = head
    fast = head
    while True:
        slow = slow.next
        fast = fast.next.next
        print slow.value, fast.value
        if slow.value == fast.value:
            return True
        elif slow is fast:
            return False

if __name__ == "__main__":
    node = create_list()
    print is_circular(node)
Improve this question
14
  • Do you mean "test that a list is circular"? Which means saying whether it's circular or not. Commented Dec 3, 2013 at 14:30
  • What is your definition of a circular list in the context of Python? You have a sequence of values, each of which references the successor? Commented Dec 3, 2013 at 14:30
  • What is your data structure? Commented Dec 3, 2013 at 14:31
  • Hi Steve, i am trying to implement right now. Commented Dec 3, 2013 at 14:51
  • 1
    Either way, it's also a duplicate of stackoverflow.com/q/34249/752320, stackoverflow.com/q/2663115/752320, and probably more . I don't think adding "python" to the question changes that. Commented Dec 3, 2013 at 14:55

4 Answers 4

Reset to default
13

A good algorithm is as follows, it may very well be the best. You do not need to copy the list or anything, like that, it can be done in constant space.

Take two pointers and set them to the beginning of the list.

Let one increment one node at a time and the other two nodes at a time.

If there is a loop at any point in the list, they will have to be pointing to the same node at some point (not including the starting point). Obviously if you reach the end of the list, there is no loop.

EDIT:
Your code, but slightly edited:

def is_circular(head):

     slow = head
     fast = head

     while fast != None:
         slow = slow.next

         if fast.next != None:
              fast = fast.next.next
         else:
              return False

         if slow is fast:
              return True

    return False
Improve this answer
Sign up to request clarification or add additional context in comments.

7 Comments

Will try that, I think this will be a good algorithm.
@sapamja If implemented correctly, it definitely works. Good luck!
HI Steve, Could you please verify, i update my code.
Thanks Steve, thats what i was looking for, learned something
+1 this is neat, I needed to scribble on a piece of paper to convince myself that it's correct. You could implement it more concisely though, e.g. the outer if head != None is unneeded (the while loop is never entered if head is None).
|
2

Don't know about best, but simpliest I can think of is

>>> import json
>>> l = []
>>> l.append(l)
>>> json.dumps(l)
Traceback (most recent call last):
  ...
ValueError: Circular reference detected
Improve this answer

1 Comment

I was looking for some kind of algorithm for interview, if you don't mind please post me a small peace of code.
1

I would test it just like in any other language:

Start traversing the list from the start, adding all visited elements into a data structure (e.g. a set) with fast insertion and lookup. If you hit the end of the list without seeing any element twice, the list is not circular. If you see an element twice, the list is circular.

If neither is true, the list is infinite. :-)

Improve this answer

1 Comment

Hi Freirich, Set should ve unique value right ? how can i insert duplicate ?
0

Here is way to do it:

  1. Start from a node & store its pointer in variable
  2. Start visiting next elements till end or the start node is revisited.
  3. if end is reached then it is not circular else circular
Improve this answer

5 Comments

din't understand the 2nd steps, how to detect end in circular linked list ?
next pointer will be null or the start node is revisited which can be checked using pointer u have stored
@VikramBhat I guess by circular OP means that there may be a loop in between
in circular it will be infinite right ?
@AbhishekBansal okay i thought he meant the circular linked list by standard definition