为何我编写的Python代码无法创建带无限环的单向链表
问题根因
- addNode实现与传参逻辑错位
你手动实例化了node0~node5共6个节点对象,本意是把这些节点依次接入链表,但addNode的实现是无论传入什么参数,都会新建一个node实例,把传入值存为新节点的val属性。
这就导致addNode构建的链和你手动创建的节点是两套完全独立的对象:addNode链上的每个节点,val属性都是你传进去的手动创建的node对象引用,只是因为node类重写了__repr__,打印时才会看起来输出的数值是0~5。
当你执行s.linkNode(node2)时,实际是把addNode构建的链上最后一个节点,接到了你手动创建的node2上——而这个手动创建的node2本身next是None,遍历到这里就停止,最终才会输出[0,1,2,3,4,5,2],根本没有形成闭环。 __repr__遍历逻辑不适配循环链表
原逻辑用tmp is not None作为循环终止条件,哪怕后续真的接成了环,遍历也会因为永远碰不到None直接死循环,耗尽内存。
修正方案
- 调整
addNode方法,兼容两种传参场景:既可以直接传入值新建节点,也可以直接传入已经实例化好的node节点接入链中:
def addNode(self, node_val_or_instance): # 判断传入的是不是已经创建好的node实例 if isinstance(node_val_or_instance, node): newNode = node_val_or_instance else: newNode = node(node_val_or_instance) if self.head is None: self.head = newNode else: tmp = self.head while tmp.nextNode is not None: tmp = tmp.nextNode tmp.nextNode = newNode
- 调整
__repr__方法,增加访问记录避免死循环,适配循环结构:
def __repr__(self): tmp = self.head val = [] visited = set() # 碰到空节点停止,碰到已经访问过的节点(说明进入环)也停止 while tmp is not None and tmp not in visited: visited.add(tmp) val.append(tmp.val) tmp = tmp.nextNode if tmp is not None: val.append(f"... 循环回到节点{tmp.val}") return "vals are %s" % val
- 原有节点创建、链接的逻辑不需要改动:修正后,执行到
s.linkNode(node2)时,会把链尾的node5的next指向node2,形成0→1→2→3→4→5→2→3→4→5…的无限循环结构,打印输出会变为vals are [0, 1, 2, 3, 4, 5, '... 循环回到节点2']
内容的提问来源于stack exchange,提问作者J JIA
相关产品推荐
相关产品推荐

