反转链表 递归 python
时间: 2025-01-16 07:07:43 浏览: 50
### 使用Python递归方法反转链表
为了实现链表的递归反转,可以定义一个`Node`类来表示单向链表中的节点。每个节点包含两个属性:数据项`data`以及指向下一个节点的链接`next`。
下面是一个完整的例子,展示了如何创建这样的节点结构并编写用于递归反转链表的方法:
```python
class Node:
def __init__(self, data=None):
self.data = data # 节点的数据部分
self.next = None # 初始设置下一节点为空
def reverse_linked_list_recursive(head):
"""递归地反转给定的链表"""
if head is None or head.next is None:
return head
new_head = reverse_linked_list_recursive(head.next)
head.next.next = head
head.next = None
return new_head
```
此函数接受当前列表的第一个节点作为参数,并返回新反转后的第一个节点。当遇到最后一个非空节点时停止递归调用,在回溯过程中改变各节点之间的指针方向[^1]。
对于测试这段代码的效果,可以通过构建简单的链表实例来进行验证:
```python
if __name__ == "__main__":
# 创建一些节点对象
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
# 构建原始顺序的链表关系
node1.next = node2
node2.next = node3
reversed_head = reverse_linked_list_recursive(node1)
current_node = reversed_head
while current_node is not None:
print(current_node.data, end=" -> " if current_node.next else "\n")
current_node = current_node.next
```
上述程序会打印出反转之后的新链表序列 `3 -> 2 -> 1`.
阅读全文
相关推荐

















