Python单链表反转：循环与递归实现详解
发布时间：2026-10-15 |
4人浏览过
本文介绍Python中单链表反转的两种核心实现方式：循环（迭代）与递归。通过定义LNode节点类，分别展示了利用指针重定向的迭代逻辑和基于栈展开的递归逻辑。文章包含完整代码示例及图解说明，帮助开发者深入理解链表操作原理。
单链表反转原理概述
针对给定的单链表，目标是将其元素顺序反转。核心思路在于调整节点间的指针指向：使原本指向后一个节点的指针改为指向前一个节点，最终将原表头指针指向原链表的最后一个节点，从而完成整体反转。
实现这一过程主要存在两种编程范式：一种是基于循环迭代的实现方式，另一种则是基于函数递归调用的实现方式。
循环迭代实现方案
首先介绍使用循环（迭代）方法来实现链表反转的具体步骤。
class LNode:
def __init__(self, elem):
self.elem = elem
self.pnext = None
def reverse(head):
if head is None or head.pnext is None: #如果输入的链表是空或者只有一个结点，直接返回当前结点
return head
pre = None #用来指向上一个结点
cur = newhead = head #cur是当前的结点。newhead指向当前新的头结点
while cur:
newhead = cur
temp = cur.pnext
cur.pnext = pre #将当前的结点的指针指向前一个结点
pre = cur
cur = temp
return newhead
if __name__=="__main__":
head = LNode(1)
p1 = LNode(2)
p2 = LNode(3)
head.pnext = p1
p1.pnext = p2
p = reverse(head)
while p:
print(p.elem)
p = p.pnext递归实现方案
其次介绍使用递归方法来实现链表反转的具体步骤。
class LNode:
def __init__(self, elem):
self.elem = elem
self.pnext = None
def reverse(head):
if not head or not head.pnext:
return head
else:
newhead = reverse(head.pnext)
head.pnext.pnext = head #令下一个结点的指针指向当前结点
head.pnext = None #断开当前结点与下一个结点之间的指针指向联系，令其指向空
return newhead
if __name__=="__main__":
head = LNode(1)
p1 = LNode(2)
p2 = LNode(3)
head.pnext = p1
p1.pnext = p2
p = reverse(head)
while p:
print(p.elem)
p = p.pnext递归过程图解分析
以下是递归过程中指针变化的详细图解说明。
本文介绍了单链表反转的两种主要实现路径，希望能为读者的学习提供有益参考，欢迎持续关注与支持。
本站声明
本文内容仅供参考，不代表本站观点。转载或引用请注明出处。如发现内容问题，请通过联系我们页面反馈。
