我如何通过递归双链表来编写反向函数。我在python中使用递归和重写来引用反向双链表的问题,但是它带给我无限循环所以我重写了逻辑但是我有点失去了上一点
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)
OUTPUT:
Head: 1
1
2
3
4
Head: 4
4
3
2
1
Is the head at a? False
Is the head at d? True
我将在这里发布我的重写反向逻辑,它现在似乎有效。免费评论它
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)