Python程序：搜索循环链表中的元素

循环链表是一种特殊的链表，其最后一个节点指向链表的第一个节点，形成一个环。搜索循环链表中的元素相对于普通链表来说稍微有些复杂，需要注意一些细节。下面我们将介绍如何用Python程序搜索循环链表中的元素。

创建循环链表

我们先来看下如何创建循环链表，以便后面搜索元素时使用。

下面是一个创建循环链表的示例代码：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next is not self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

上述代码中，我们定义了一个Node类，表示链表中的一个节点，具体包括data和next两个属性，分别表示当前节点的值和下一个节点。

然后定义了一个CircularLinkedList类，表示循环链表，具体包括head属性，表示链表的头节点。

接着我们定义了add_node()方法，用于向链表中添加节点。如果当前链表为空链表，那么直接将头节点指向新节点，并将新节点的next指向头节点（因为是循环链表）。如果不是空链表，那么遍历链表到最后一个节点，然后将其next指向新节点，并将新节点的next指向头节点。

搜索循环链表中的元素

有了上述基础，我们现在可以来看下如何搜索循环链表中的元素。

下面是一个搜索循环链表中元素的示例代码：

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next is not self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def search_node(self, key):
        if self.head is None:
            return None
        else:
            current = self.head
            while current.data != key:
                if current.next is self.head:
                    return None
                current = current.next
            return current

上述代码中，我们在CircularLinkedList类中添加了search_node()方法，用于搜索循环链表中是否存在某个特定元素。如果链表为空，那么返回None。否则从头节点开始遍历链表，如果找到了与key相等的节点，则返回该节点，否则直至遍历到头节点仍未找到，返回None。

搜索循环链表中的元素（另一种方法）

除了上述方法外，我们还可以使用快慢指针的方式来搜索循环链表中的元素，其实现比较简单。

下面是另一种搜索循环链表中元素的示例代码：

class Node:
    def __init__(self, data=None):
        self.data = data
        self.next = None

class CircularLinkedList:
    def __init__(self):
        self.head = None

    def add_node(self, data):
        new_node = Node(data)
        if self.head is None:
            self.head = new_node
            new_node.next = self.head
        else:
            current = self.head
            while current.next is not self.head:
                current = current.next
            current.next = new_node
            new_node.next = self.head

    def search_node(self, key):
        if self.head is None:
            return None
        else:
            slow = self.head
            fast = self.head.next
            while True:
                if fast is None or fast.next is None:
                    return None
                elif slow.data == key or fast.data == key:
                    return slow if slow.data == key else fast
                else:
                    slow = slow.next
                    fast = fast.next.next
                    if slow == fast:
                        return None

上述代码中，我们同样定义了Node和CircularLinkedList类，用来表示循环链表。在search_node()方法中，我们采用快慢指针的方式来搜索元素。首先设定一个slow指针和一个fast指针，slow每次移动一步，fast每次移动两步。如果fast指针移动到了链表末尾或最后一个节点的下一个节点，那么说明该链表中没有要搜索的元素，返回None；如果找到了要搜索的元素，则返回其对应的节点；如果快慢指针相遇，那么说明链表中存在环，返回None。

测试

为了验证上述两种方法的正确性，我们需要编写一些测试用例。

下面是一个测试循环链表中搜索元素的代码：

if __name__ == '__main__':
    cl = CircularLinkedList()
    cl.add_node(1)
    cl.add_node(2)
    cl.add_node(3)
    cl.add_node(4)
    cl.add_node(5)

    node = cl.search_node(3)
    print(node.data)  # 输出3

    node = cl.search_node(6)
    print(node)  # 输出None

上述代码中，我们新建了一个循环链表，并往其中添加了5个节点。接着分别测试搜索循环链表中存在和不存在的元素，分别输出其对应节点的值和None。