用栈倒转链表中的节点，为什么新的链表变得这么大?

Question

我想在一个有堆栈的链表中反转节点。所以我首先创建一个链表:

head = ListNode(0)
temp = head
temp.next = ListNode(1)
temp = temp.next
temp.next = ListNode(2)

然后我使用stack来存储列表节点，然后将它们弹出到一个新的链表new_tail来反转给定的链表。

dummy_node = ListNode(0)
cur = head
new_tail = dummy_node
while cur:
i = 0
tmp_sk = [] # use the stack to store the elements of linked list
tmp_tail = cur 
while i < 3:        
if cur:
tmp_sk.append(cur)
cur = cur.next
i +=1
else:
new_tail.next = tmp_tail
break
while tmp_sk:
new_tail.next = tmp_sk.pop()
new_tail = new_tail.next

但是奇怪的事情发生了。当我尝试打印新的链表时，链表非常大。

count = 0
new = dummy_node
while new:
count+=1
print(new.val)
new = new.next

计数可以是很大的数字，打印不能停止，直到我干预。我找不到问题出在哪里。

Answer 1

几个问题:

• 主要问题是在while tmp_sk循环中附加的最后一个节点仍将具有未重置的next引用。因此，当while tmp_sk完成时，您有一个链表，其最后一个节点是new_tail，但该节点不是真正的尾:它有一个从未更新过的next引用，并且引用最初是第二个节点的节点，现在是最后一个节点。这样就形成了一个循环。解决方案是在该循环之后执行new_tail.next = None。

• 内循环不应该以i < 3作为条件。这只会在列表有三个节点时起作用。您应该将其设置为通用的，并测试cur。这也意味着循环中的else块永远不会被执行。

• 外环while cur:不起作用。一旦循环进行了一次迭代，它将永远退出。如果它要进行第二次迭代并使用新堆栈重新启动，那么它就没有意义了，等等。所以去掉这个循环，只保留它的主体。

• 打印列表的部分，也打印虚拟节点的值。我不认为这是目的;所以跳过第一个节点。

• 这不是问题，但是你应该把你的代码分成函数，每个函数负责一个任务:创建列表，反转列表，打印列表。

这是你的代码的更正和清理:

class ListNode:
def __init__(self, val):
self.val = val
self.next = None
def createList(values):
# initialise list (generic - from a list of values)
node = dummy = ListNode(None)
for val in values:
node.next = ListNode(val)
node = node.next
return dummy.next
def reverseList(head):
cur = head
tmp_sk = [] # use the stack to store the elements of linked list
while cur:
tmp_sk.append(cur)
cur = cur.next
dummy_node = ListNode(None)
new_tail = dummy_node
while tmp_sk:
new_tail.next = tmp_sk.pop()
new_tail = new_tail.next
new_tail.next = None # this was missing!
return dummy_node.next  # return the new head
def printList(head):
cur = head
while cur:
print(cur.val)
cur = cur.next
# main program
head = createList([0, 1, 2])
head = reverseList(head)
printList(head)