假设 x 和 y 是循环链表的节点但不必属于同⼀个链表。请给出⼀个快速有 效的代码实现在 5circular_queuepy 基础上完成即补全⽅法 same_queuexy 的代码并输出正确的测试结果。
class Node:
def __init__(self, data=None):
self.data = data
self.next = None
class CircularQueue:
def __init__(self):
self.tail = None
def enqueue(self, data):
node = Node(data)
if self.tail is None:
self.tail = node
node.next = self.tail
else:
node.next = self.tail.next
self.tail.next = node
self.tail = node
def dequeue(self):
if self.tail is None:
return None
elif self.tail.next == self.tail:
node = self.tail
self.tail = None
return node.data
else:
node = self.tail.next
self.tail.next = node.next
return node.data
def is_empty(self):
return self.tail is None
def print_queue(self):
if self.tail is None:
print("Empty queue")
else:
current = self.tail.next
while current != self.tail:
print(current.data, end=" -> ")
current = current.next
print(current.data)
def same_queue(x, y):
"""
判断节点 x 和 y 是否属于同一个循环链表
"""
if x is None or y is None:
return False
# 判断 x 所在的链表是否与 y 所在的链表相同
current = x.next
while current != x:
if current == y:
return True
current = current.next
# 判断 y 所在的链表是否与 x 所在的链表相同
current = y.next
while current != y:
if current == x:
return True
current = current.next
return False
# 测试代码
q1 = CircularQueue()
q1.enqueue(1)
q1.enqueue(2)
q1.enqueue(3)
q2 = CircularQueue()
q2.enqueue(4)
q2.enqueue(5)
q2.enqueue(6)
node1 = q1.tail.next
node2 = q1.tail.next.next
node3 = q2.tail.next.next
node4 = Node(7)
print(same_queue(node1, node2)) # True
print(same_queue(node1, node3)) # False
print(same_queue(node1, node4)) # False
原文地址: https://www.cveoy.top/t/topic/bw0R 著作权归作者所有。请勿转载和采集!