如何用递归为双向链表编写反转函数。我参考了关于使用递归反转双向链表的问题,并在Python中重新编写了代码,但它导致了无限循环,所以我重新思考了逻辑,但我有点忘记了prev指针。
class Node:
def __init__(self, data, prev=None, nxt=None):
self.val = data
self.prev = prev
self.next = nxt
class DoublyLinkedList:
def __init__(self, head):
self.head = head
def print_list(self):
cur = self.head
while cur is not None:
print(cur.val)
cur = cur.next
def reverse(self):
if self.head is None or self.head.next is None: return self.head
cur = self.head
def reverse_node(node):
if node is None: return
if node.next is None:
node.prev = None
return node
new_head = reverse_node(node.next)
new_node = node.next
tmp = new_node.next
new_node.prev = tmp
new_node.next = node
node.next = None
return new_head
self.head = reverse_node(cur)
a = Node(1, prev=None)
b = Node(2, prev=a)
c = Node(3, prev=b)
d = Node(4, prev=c)
a.next = b
b.next = c
c.next = d
dll = DoublyLinkedList(a)
dll.print_list()
dll.reverse()
dll.print_list()
dll.reverse()
更改为dll.reverse_recursive()
,我似乎让它正常工作了。列表倒序打印,头指向具有val=4
的元素。您能否更详细地描述一下您的代码正在做什么不需要的事情? - Hoog