以非递归方式反转链表

Question

请检查下面的反转功能。剩下的代码应该没问题。由于某种原因，该函数没有反转双链接列表。

#!/bin/python3
import math
import os
import random
import re
import sys

双链表节点结构

class DoublyLinkedListNode:
    def __init__(self, node_data):
        self.data = node_data
        self.next = None
        self.prev = None

双链表结构

class DoublyLinkedList:
    def __init__(self):
        self.head = None
        self.tail = None

    def insert_node(self, node_data):
        node = DoublyLinkedListNode(node_data)

        if not self.head:
            self.head = node
        else:
            self.tail.next = node
            node.prev = self.tail
            self.tail = node

按从头部到尾部的顺序排列。

def print_doubly_linked_list(node, sep, fptr):
    while node:
        fptr.write(str(node.data))

        node = node.next

        if node:
            fptr.write(sep)

请检查下面的反向函数，因为此函数不会返回反向双链接列表。检查是否有任何错误并让我知道。

def reverse(head):
    if head == None:
        return head
    temp = None    
    curr = head
    while(curr is not None):
        temp = curr.prev
        curr.prev = curr.next
        curr.next= temp
        curr = curr.next
    if temp is not None:
        head = temp.prev
    return head




if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    t = int(input())

    for t_itr in range(t):
        llist_count = int(input())

        llist = DoublyLinkedList()

        for _ in range(llist_count):
            llist_item = int(input())
            llist.insert_node(llist_item)

        llist1 = reverse(llist.head)

        print_doubly_linked_list(llist1, ' ', fptr)
        fptr.write('\n')

    fptr.close()

Answer 1

您开始从标题开始反转列表，该标题没有prev项，因此将从while循环中打断。相反，从尾部反转应该：

llist1 = reverse(llist.tail)

一般来说，我认为你的函数reverse应该把整个列表（而不是头部或尾部）作为参数，然后根据其中的项目构建一个全新的DoublyLinkedList。这还可以解决与变量名之间的混淆，其中llist是DoublyLinkedList，而llist1是DoublyLinkedListNode。

编辑：我忘了，在insert_node中，您还应该制作self。tail=节点如果还没有头节点/第一个节点。