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
假设 x 和 y 是循环链表的节点但不必属于同⼀个链表。请给出⼀个快速有 效的代码实现在 5circular_queuepy 基础上完成即补全⽅法 same_queuexy 的代码并输出正确的测试结果。

原文地址: https://www.cveoy.top/t/topic/bw0R 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录