Last active
August 29, 2015 14:23
-
-
Save andreagrandi/dd9538d9e68faf7f2e97 to your computer and use it in GitHub Desktop.
Python Linked List: prevent the list to become circular
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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