我想弄清楚如何使用 Recursion 在 Python 中遍历链表。
我知道如何使用常见循环遍历链表,例如:
item_cur = my_linked_list.first
while item_cur is not None:
print(item_cur.item)
item_cur = item_cur.next
我想知道如何将这个循环变成递归步骤。
谢谢
你可以这样做:
def print_linked_list(item):
# base case
if item == None:
return
# lets print the current node
print(item.item)
# print the next nodes
print_linked_list(item.next)
试试这个。
class Node:
def __init__(self,val,nxt):
self.val = val
self.nxt = nxt
def reverse(node):
if not node.nxt:
print node.val
return
reverse(node.nxt)
print node.val
n0 = Node(4,None)
n1 = Node(3,n0)
n2 = Node(2,n1)
n3 = Node(1,n2)
reverse(n3)
看起来你的链接列表有两种部分。您有具有
next
和 item
属性的列表节点,以及一个具有指向 first
节点的属性的包装对象。要递归打印列表,您需要有两个函数,一个用于处理包装器,另一个辅助函数用于对节点进行递归处理。
def print_list(linked_list): # Non-recursive outer function. You might want
_print_list_helper(linked_list.first) # to update it to handle empty lists nicely!
def _print_list_helper(node): # Recursive helper function, gets passed a
if node is not None: # "node", rather than the list wrapper object.
print(node.item)
_print_list_helper(node.next) # Base case, when None is passed, does nothing