Python链表反转详解：迭代与递归两种实现方式

晚来风

发布时间：2026-10-13 | 6人浏览过

原创

本文详细解析Python中单向链表反转的两种核心实现方式：循环迭代与递归。通过定义Node类，分别演示了利用pre、head、next三个指针进行迭代反转的过程，以及通过递归找到临界点后反向链接节点的逻辑。文章包含完整代码示例及测试输出，帮助开发者深入理解链表操作原理。

链表反转概述

链表反转是数据结构与算法中一道基础且常见的题目。其核心任务是将输入的单向链表逆序输出，具体转换效果如示意图所示。实现这一功能主要包含两种主流方法：一种是基于循环迭代的思路，另一种则是利用递归机制。

循环迭代法实现

方法一：循环迭代法

在循环迭代算法中，需要引入三个临时变量：pre（前驱节点）、head（当前节点）和next（后继节点）。该算法的临界条件判断包括：当链表为空（None）或链表仅包含一个节点时，直接返回当前头指针即可。


# encoding: utf-8
class Node(object):
def __init__(self):
self.value = None
self.next = None
def __str__(self):
return str(self.value)
def reverse_loop(head):
if not head or not head.next:
return head
pre = None 
while head:
next = head.next # 缓存当前节点的向后指针，待下次迭代用
head.next = pre # 这一步是反转的关键，相当于把当前的向前指针作为当前节点的向后指针
pre = head # 作为下次迭代时的（当前节点的）向前指针
head = next # 作为下次迭代时的（当前）节点
return pre # 返回头指针，头指针就是迭代到最后一次时的head变量（赋值给了pre）

以下是具体的测试代码示例：


if __name__ == '__main__':
three = Node()
three.value = 3
two = Node()
two.value = 2
two.next = three
one = Node()
one.value = 1
one.next = two
head = Node()
head.value = 0
head.next = one
newhead = reverse_loop(head)
while newhead:
print(newhead.value, )
newhead = newhead.next

运行上述代码后的输出结果如下：

递归法实现

方法二：递归法

递归方法的核心思想在于：


head.next = None
head.next.next = head.next
head.next.next.next = head.next.next
...
...

将head节点的后向指针所指向节点的next指针，重新指向head节点本身，并依此类推，逐步完成链表的反向连接。

实现递归的关键在于确定递归终止的临界点，即何时退出递归调用。当判断head.next为None时，表明当前节点已是链表的最后一个节点，此时不再进行递归调用，直接返回该节点作为新链表的头节点。


def reverse_recursion(head):
if not head or not head.next:
return head
new_head = reverse_recursion(head.next)
head.next.next = head
head.next = None
return new_head

以上就是本文的全部内容，希望能为各位的学习提供有益的帮助，同时也欢迎大家继续支持本站获取更多技术资源。