非递归反转链表

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)

请检查下面的反向函数，因为此函数不 return 反向双向链表。检查是否有任何错误并告诉我。

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

你从 head 开始反转你的列表，它没有 prev 项，因此 breaks 在你的 while 循环之外。相反，从 tail 反转应该做：

llist1 = reverse(llist.tail)

一般来说，我认为你的函数 reverse 应该将整个列表（不是头或尾）作为参数，然后从其中的项目构建一个全新的 DoublyLinkedList。这也将解决变量名称的混淆，其中 llist 是 DoublyLinkedList 而 llist1 是 DoublyLinkedListNode.

编辑：我忘了，在 insert_node 中，如果还没有 head/第一个节点，你也应该创建 self.tail = node。

非递归反转链表

reverse a linked list non recursive

python-3.x

doubly-linked-list