Aug-14-2019, 07:51 AM
My book has this exercise:
R-7.6 Suppose that x and y are references to nodes of circularly linked lists,
although not necessarily the same list. Describe a fast algorithm for telling
if x and y belong to the same list.
I wonder if there is the FAST algorithm of checkSamecircularList(x, y) without L CircularList ref but find ref to L from the first element x... can do this??? after check if y is in this List of x... well ?
checkSamecircularList(L, x, y):
result
RESTART: F:/DOWNLOADS/Textbooks - Source Code/Python DS Tamassia/ch07/exe/R-7-6.py
same list x, y of L: True
same list x1, y of L: False
same list x1, y1 of L: False
same list x1, y1 of L1: True
>>>
R-7.6 Suppose that x and y are references to nodes of circularly linked lists,
although not necessarily the same list. Describe a fast algorithm for telling
if x and y belong to the same list.
I wonder if there is the FAST algorithm of checkSamecircularList(x, y) without L CircularList ref but find ref to L from the first element x... can do this??? after check if y is in this List of x... well ?
checkSamecircularList(L, x, y):
result
RESTART: F:/DOWNLOADS/Textbooks - Source Code/Python DS Tamassia/ch07/exe/R-7-6.py
same list x, y of L: True
same list x1, y of L: False
same list x1, y1 of L: False
same list x1, y1 of L1: True
>>>
if __name__ == '__main__':
# Function to find sum of the given
# Circular linked list
def checkSamecircularList(L, x, y):
temp = L._tail # head
# tsum = temp.data
temp = temp._next
xyes = False
yyes = False
while(temp is not L._tail):
if temp is x:
xyes = True
if temp is y:
yyes = True
temp = temp._next
return xyes and yyes
L = CircularQueue()
L.enqueue(1)
L.enqueue(2)
L.enqueue(3)
L.enqueue(4)
L.enqueue(5)
L1 = CircularQueue()
L1.enqueue(1)
L1.enqueue(2)
L1.enqueue(3)
L1.enqueue(4)
L1.enqueue(5)
x = L.first()
y = (L.first())._next
x1 = L1.first()
y1 = (L1.first())._next
print("same list x, y of L: " + str(checkSamecircularList(L, x, y)) )
print("same list x1, y of L: " + str(checkSamecircularList(L, x1, y)) )
print("same list x1, y1 of L: " + str(checkSamecircularList(L, x1, y1)) )
print("same list x1, y1 of L1: " + str(checkSamecircularList(L1, x1,y1)) )
