为什么我不能创建带圆圈的链表？

Question

我正在尝试创建一个带有无限圆的链表，如0->1->2->3->4->5-**>2**->3->4->5-**>2**->3->4->5-> .........，下面是我的代码：

class node():
def __init__(self, val):
self.val = val
self.nextNode = None

def __repr__(self):
return "%s" % self.val

class linkedList():
def __init__(self):
self.head = None
def addNode(self, nodeVal):
newNode = node(nodeVal)
if self.head is None:
self.head = newNode
else:
tmp = self.head
while tmp.nextNode is not None:
tmp = tmp.nextNode
tmp.nextNode = newNode

def linkNode(self, node):
if self.head is None:
raise Exception("list can't be None")
tmp = self.head
while tmp.nextNode is not None:
tmp = tmp.nextNode
tmp.nextNode = node

def __repr__(self):           
tmp = self.head
val = []
while tmp is not None:
val.append(tmp.val)
tmp = tmp.nextNode
return "vals are %s" % val

s = linkedList()
head = node(0)
node1 = node(1)
node2 = node(2)
node3 = node(3)
node4 = node(4)
node5 = node(5)
s.addNode(head)
s.addNode(node1)
s.addNode(node2)
s.addNode(node3)
s.addNode(node4)
s.addNode(node5)
s.linkNode(node2)
print(s)

但输出是这样的：vals是[0, 1, 2, 3, 4, 5, 2]，它不是一个圆。

Answer 1

由于方法addNode需要一个值，并将为其创建一个节点，因此不应使用节点作为参数来调用它。

因此，在不更改类方法的情况下，您的主要代码可以如下所示。顺便说一句，我发现s对列表来说是个坏名字——它通常用于字符串——所以我把它命名为lst：

lst = linkedList()
lst.addNode(0)
lst.addNode(1)
lst.addNode(2)
lst.addNode(3)
lst.addNode(4)
lst.addNode(5)
lst.linkNode(lst.next.next)
print(lst)

不相关，但这里有一些提高你的课程的方法：

• 由于addNode每次都需要遍历整个列表，因此您的链表可能需要维护对尾部节点的引用。通过这种方式，您可以在恒定时间内在末尾附加一个新节点。

• addNode也可以返回新添加的节点，因此您可以稍后使用它来调用linkNode

以下是您的代码在实现这些想法后的样子：

def __init__(self):
self.head = None
self.tail = None
def addNode(self, nodeVal):
newNode = node(nodeVal)
if self.head is None:
self.head = newNode
else:
self.tail.next = newNode
self.tail = newNode
return newNode

def linkNode(self, node):
if self.head is None:
raise Exception("list can't be None")
self.tail.next = node
# Main code
lst = linkedList()
lst.addNode(0)
lst.addNode(1)
backref = lst.addNode(2)
lst.addNode(3)
lst.addNode(4)
lst.addNode(5)
lst.linkNode(backref)
print(lst)

Answer 2

之所以会发生这种情况，是因为在addNode中，您正在通过执行来创建一个新节点

newNode = node(nodeVal)

这意味着当您稍后将node2传递给linkNode时，它仍然是由class Node创建的具有nextNode=None的节点

只要去掉那条线，你就可以走了。

Answer 3

需要一个小细节，然后它应该按您的意愿工作。

• 将线路s.linkNode(node2)替换为s.linknode(s.head.nextNode.nextNode)

然后使用以下方法打印循环中的x个第一个元素：

tmp = s.head
for i in range(x):
print(tmp.val)
tmp = tmp.nextNode

• 注意不要执行print(s)，因为这将在循环中执行无限循环

前面的不起作用的原因是，函数addNode()中有下面的newNode = node(nodeVal)，因此它创建了与列表没有连接的新节点。