将链接列表中的节点与堆栈相反。为什么新链接列表变得如此之大？

Question

我想在链接列表中使用stack反向节点。因此，我首先创建一个链接列表：

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

几个问题：

• 主要问题是中附加的最后一个节点，而tmp_sk循环仍将具有未重置的下一个参考。因此，当tmp_sk完成时，您有一个链接列表，其最后一个节点是new_tail，但是该节点不是真正的 a tail：it具有从未更新的Next参考，并指的是最初是第二个节点的节点，现在是一个但持久的节点。因此，现在有一个周期。解决方案是执行new_tail.next = none在该循环之后。

• 内部循环不应具有i＆lt; 3作为条件。这只有在您的列表有三个节点时才能起作用。您应该制作此通用，然后测试cur。这也意味着该循环中的else块永远不会执行。应该省略它。

• 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)