环形链表代码陷入无限循环问题求助（附自定义实现代码）

首先，咱们来看你的代码里导致无限循环的核心原因：insert_first方法没有正确维护环形链表的闭合结构，使得插入节点后链表的环断裂了，进而让__iter__遍历逻辑陷入死循环。

问题分析 #

你的CircularList初始化时，创建了一个哨兵节点（data=None），它的next指向自己，形成一个空的环。但当你调用insert_first插入新节点时，只做了两步：

• 新节点的next指向当前的self.first
• 更新self.first为新节点

这就导致原来的哨兵节点的next仍然指向自己，并没有指向新节点。举个例子：

1. 初始化后：哨兵 -> 哨兵
2. 插入节点10后：10 -> 哨兵 -> 哨兵

此时链表根本不是一个完整的环——10的下一个是哨兵，但哨兵的下一个还是自己，不是10。这时候__iter__遍历：

• 从10开始，current.next是哨兵，不等于起始的10，于是yield 10，current变成哨兵
• 哨兵的next是自己，仍然不等于起始的10，于是再次yield哨兵，current还是哨兵，无限循环下去

修复方案 #

我们需要修改insert_first方法，确保每次插入新节点后，链表的环始终闭合：插入新节点时，找到链表的最后一个节点（也就是next指向当前self.first的节点），把它的next指向新节点，再让新节点的next指向原来的self.first，最后更新self.first为新节点。

修复后的完整代码：

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

class CircularList(object):
    def __init__ ( self ):
        self.first = Link(None, None)
        self.first.next = self.first  # 初始化空环
    
    def insert_first ( self, item ):
        new_link = Link(item)
        # 如果是空环（只有哨兵节点）
        if self.first.next == self.first:
            new_link.next = self.first
            self.first.next = new_link
        else:
            # 找到最后一个节点（next指向当前self.first的节点）
            current = self.first
            while current.next != self.first:
                current = current.next
            # 让最后一个节点指向新节点
            current.next = new_link
            # 新节点指向原来的first
            new_link.next = self.first
        # 更新first为新节点
        self.first = new_link
    
    def __iter__(self):
        current = self.first
        first = current
        while current.next != first:
            yield current
            current = current.next
    
    def __str__(self):
        # 实现字符串输出，方便测试
        nodes = []
        for link in self:
            nodes.append(str(link.data))
        return " -> ".join(nodes)

# 测试一下
clist = CircularList()
clist.insert_first(10)
clist.insert_first(20)
clist.insert_first(30)
print(clist)  # 输出: 30 -> 20 -> 10
# 遍历测试，不会无限循环
for node in clist:
    print(node.data)

额外说明 #

• 修复后的insert_first保证了每次插入后，链表始终是一个闭合的环：最后一个节点的next永远指向当前的self.first
• __iter__方法的逻辑是正确的，只要环是闭合的，它就会在遍历回到起始节点时停止，不会无限循环
• 新增的__str__方法可以帮助你直观查看链表内容，方便调试

内容的提问来源于stack exchange，提问作者Eric Kim