Fastest way to prove linked list is circular ? in python

Question

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)

Do you mean "_test_ that a list is circular"? Which means saying whether it's circular or not. — Guido, Dec 03 '13 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? — Frerich Raabe, Dec 03 '13 at 14:30
@SteveP. FWIW, My vote was for lack of effort shown, not clarity. If you feel the close *reason* should be changed, you can [always flag it](http://meta.stackexchange.com/a/208772/212780), but I *don't* think it's a candidate to be reopened as it stands now. — Geobits, Dec 03 '13 at 14:53
Either way, it's *also* a duplicate of http://stackoverflow.com/q/34249/752320, http://stackoverflow.com/q/2663115/752320, and probably more . I don't think adding "python" to the question changes that. — Geobits, Dec 03 '13 at 14:55
@Geobits I voted it for the same reason (lack of effort). However this option does not show in the cited options. :( — Abhishek Bansal, Dec 03 '13 at 14:59
please hold on m writing my code now. thanks for the suggestion. my question was too eary to ask. — , Dec 03 '13 at 15:02
@Geobits That's like saying there should only be one BFS or DFS question, yet there's obviously many of them. He showed code, this is not a duplicate IMHO. — Steve P., Dec 03 '13 at 15:29
@SteveP. No, that's comparing two different things. That's like saying there should only be one "linked list" question, which is untrue. However, I don't see a need for multiple "*How to find a cycle in a LL?*" questions, especially since **every one of them has same basic answer**, tortoise/hare, fast/slow, whatever you call it. — Geobits, Dec 03 '13 at 15:40
@Geobits I understand what you're saying, but there's only one way to one or two good ways to reverse a linked list, and I guarantee there are multiple questions across different languages for that...I dunno, don't really care tbh. It's not a big deal to me either way. — Steve P., Dec 03 '13 at 15:44
Your edited code is not quite right. What is `node.value`? What happens if there is no cycle, and `head` gets to the end of the list? — Teepeemm, Dec 03 '13 at 17:47

Steve P. · Accepted Answer · 2016-05-06T18:07:19.810

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

edited May 06 '16 at 18:07

answered Dec 03 '13 at 14:37

Steve P.

14,489
8
42
72

1

Will try that, I think this will be a good algorithm. – Dec 03 '13 at 14:41
@sapamja If implemented correctly, it definitely works. Good luck! – Steve P. Dec 03 '13 at 14:41
HI Steve, Could you please verify, i update my code. – Dec 03 '13 at 15:08
Thanks Steve, thats what i was looking for, learned something – Dec 03 '13 at 15:31
+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`). – Frerich Raabe Dec 03 '13 at 18:25
The way this is coded does not work. It will return True for any linked list greater than 2. Slow and fast both start at index 0. The first time around the loop, slow is index 1, and fast is index 2. The next time around both slow and fast are at index two, and the algorithm returns True because you check if slow is fast before you increment fast. You need to remove the first if slow is fast. – calthoff May 06 '16 at 04:43
@calthoff good call :) – Steve P. May 06 '16 at 18:07

score 2 · Answer 2 · answered Dec 03 '13 at 14:32

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

answered Dec 03 '13 at 14:32

alko

46,136
12
94
102

I was looking for some kind of algorithm for interview, if you don't mind please post me a small peace of code. – Dec 03 '13 at 14:36

score 1 · Answer 3 · answered Dec 03 '13 at 14:32

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. :-)

answered Dec 03 '13 at 14:32

Frerich Raabe

90,689
19
115
207

Hi Freirich, Set should ve unique value right ? how can i insert duplicate ? – Dec 03 '13 at 14:34

score 0 · Answer 4 · answered Dec 03 '13 at 14:36

0

Here is way to do it:

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

answered Dec 03 '13 at 14:36

Vikram Bhat

6,106
3
20
19

din't understand the 2nd steps, how to detect end in circular linked list ? – Dec 03 '13 at 14:37
next pointer will be null or the start node is revisited which can be checked using pointer u have stored – Vikram Bhat Dec 03 '13 at 14:40
@VikramBhat I guess by circular OP means that there may be a loop in between – Abhishek Bansal Dec 03 '13 at 14:41
in circular it will be infinite right ? – Dec 03 '13 at 14:42
@AbhishekBansal okay i thought he meant the circular linked list by standard definition – Vikram Bhat Dec 03 '13 at 14:44

Fastest way to prove linked list is circular ? in python

4 Answers4

Linked