Skip to content

Instantly share code, notes, and snippets.

@andreagrandi
Last active August 29, 2015 14:23
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save andreagrandi/dd9538d9e68faf7f2e97 to your computer and use it in GitHub Desktop.
Save andreagrandi/dd9538d9e68faf7f2e97 to your computer and use it in GitHub Desktop.
Python Linked List: prevent the list to become circular
def is_list_circular(l):
slower = l
faster = l.get_next()
while True:
# if faster pointer finds a None element
# then the list is not circular
if (faster is None) or (faster.get_next() is None):
return False
# if faster element catch up with the slower
# then the list is circular
elif (faster == slower) or (faster.get_next() == slower):
return True
# in any other case we just move slower by one
# and faster by two steps
else:
slower = slower.get_next()
faster = faster.get_next().get_next()
class ListElement(object):
def __init__(self):
self._next = None
def add_next(self, next_node):
self._next = next_node
# check if the list, with the added element
# is circular. If it is, then remove the just
# added element.
if is_list_circular(self):
self._next = None
def get_next(self):
return self._next
# I create 4 separate ListElement
a = ListElement()
b = ListElement()
c = ListElement()
d = ListElement()
# I chain them and in particular I try to connect element d to a
a.add_next(b)
b.add_next(c)
c.add_next(d)
d.add_next(a)
# I expect the first three to have a next element
# but the fourth to have None
assert a.get_next() is not None
assert b.get_next() is not None
assert c.get_next() is not None
assert d.get_next() is None
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment