python-3.x - 通过递归方式反向双向链表不在python中迭代
问题描述
我如何通过递归为双链表编写反向函数。我已经在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()
解决方案
我所做的只是在最后添加一些打印输出,看看在哪里。在我看来,您的代码就像您期望的那样。在reverse()
功能之后,头部似乎清楚地指向d
而不是a
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
cur = self.head
def reverse_node(node):
if node is None: return node
node.next, node.prev = node.prev, node.next
if node.prev is None: return node
return reverse_node(node.prev)
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)
print("Head: ",dll.head.val)
dll.print_list()
dll.reverse()
print()
print("Head: ",dll.head.val)
dll.print_list()
print("Is the head at a? ",dll.head is a)
print("Is the head at d? ",dll.head is d)
输出:
Head: 1
1
2
3
4
Head: 4
4
3
2
1
Is the head at a? False
Is the head at d? True
推荐阅读
- arrays - 在范围内看不到数组我不确定为什么 SwiftUI
- python - pandas 结合了两个值
- css - 在 React 中使用 CSS 进行样式设置
- typescript - 打字稿:从另一种类型的可选属性中构造具有所需属性的新类型
- field - Word 公式字段在标题中未正确显示
- python - 如何一次对字典或列表中的所有嵌套字典和列表进行排序?
- python - ModuleNotFoundError:旧版本的 pytorch 没有名为“火炬”的模块
- javascript - 如何将 required = false 更改为所需的输入
- ios - iOS 上的 Firebase AppCheck:403 权限错误 - PERMISSION_DENIED
- java - 易失性变量读取行为