Python递归与迭代实现链表反转详解
发布时间：2026-10-15| 4人浏览过
本文详细介绍如何使用Python通过递归和迭代两种方法实现链表反转。首先定义链表节点结构，接着演示如何构建链表并遍历打印。重点解析递归法的三要素（函数功能、结束条件、缩小范围）及具体代码实现，同时提供迭代法的完整逻辑与代码。包含完整的测试用例及输出结果分析，帮助读者深入理解链表操作。
链表节点定义与基础操作
首先需要定义链表节点（ListNode）的数据结构，包含数据域和指向下一个节点的指针。
class ListNode:
def __init__(self,data):
self.data = data
self.next = None接下来编写函数，将给定的列表L转换为链表结构。
def make_list(L):
具体初始化过程：创建头节点，遍历列表剩余元素，依次创建新节点并连接，最后返回头节点。
head = ListNode(L[0])
cur = head
for i in L[1:]:
cur.next = ListNode(i)
cur = cur.next
return head
定义遍历函数，用于打印链表中的所有元素，便于后续验证反转效果。
def print_list(head):
cur = head
while cur != None:
print(cur.data,end=' ')
cur = cur.next
递归法反转链表实现
介绍使用递归方法反转链表的核心逻辑。
def reverse_list(head):递归实现需明确以下三个关键要素：
- 1. 明确函数功能：该函数负责反转当前链表，并返回新的头节点。
- 2. 确定结束条件：当链表为空（head为None）或仅包含一个节点（head.next为None）时，直接返回当前头节点。
if head==None or head.next==None:
return head- 3. 确定等价条件（缩小问题规模）：对于数组，范围缩小是n到n-1；对于链表，可以考虑处理
head之后的子链表，即递归处理head.next节点。
>head.next
reverse = reverse_list(head.next) #假设reverse是head以后的、已经反转过的链表在递归返回后，需要将当前head节点连接到已反转的子链表（reverse）上，具体操作是将head.next指向reverse，并断开原next连接。
tmp = head.next
tmp.next = head
head.next = None
return reverse #返回新的列表迭代法反转链表与测试验证
介绍使用迭代方法反转链表的实现方案。
def reverse_list2(head):
#print_list(head)
cur = head
pre = None
while cur:
tmp = cur.next
cur.next = pre
pre = cur
cur = tmp
head = pre
return head
if __name__ == '__main__':
L = [3,2,7,8]
head = make_list(L)
演示如何正序打印原始链表，以对比反转前后的状态。
print('原始list：')
print_list(head)
print('\n')
展示调用递归反转函数后，打印反转后的链表结果。
revere = reverse_list(head)
print('反转一次的list：')
print_list(revere)
print('\n')
展示再次调用迭代反转函数（reverse_list2）后的打印结果，并分析head节点在多次反转后的变化。
print('head is')
print_list(head) #发现此时head节点变成了最后一个节点，说明函数是对head这个实例直接作用的
print('\n')
# print('revere is')
# print_list(revere)
# print('\n')
print('反转两次的list：')
print_list(reverse_list2(revere))
以上就是Python利用递归和迭代方法实现链表反转的完整介绍。如需了解更多Python链表相关技术，可参考本站其他文章或继续浏览后续内容，感谢支持。
免责声明：本文内容仅供参考，不代表本站观点。转载或引用请注明出处。
