用stack反转链表中的节点，为什么新链表变得这么大？

Question

我想反转链表中的节点 stack.so 我首先创建一个链表：

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 从未更新过的引用，指的是原来是第二个节点的节点，现在是 one-but-last 节点。所以现在有一个循环。解决方案是在该循环之后立即执行 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)

用stack反转链表中的节点，为什么新链表变得这么大？

Reverse the nodes in linked list with stack .why the new linked list become so large?

python

stack

linked-list