Python 中如何遍历链表

Question

我想弄清楚如何使用Recursion在 Python 中遍历链表。

我知道如何使用常见循环遍历链表，例如：

 item_cur = my_linked_list.first
       while item_cur is not None:
           print(item_cur.item)
           item_cur = item_cur.next  

我想知道如何将这个循环变成递归步骤。

谢谢

Answer 1

你可以这样做：

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)

Answer 2

尝试这个。

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)