我正在尝试通过递归在Python中遍历链表。
我知道如何使用常见的循环(例如for循环和while循环)遍历链表:
item_cur = my_linked_list.first
while item_cur is not None:
print(item_cur.item)
item_cur = item_cur.next
我想知道如何将这个循环转换为递归步骤。
谢谢。
我正在尝试通过递归在Python中遍历链表。
我知道如何使用常见的循环(例如for循环和while循环)遍历链表:
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