Python实现单链表反转：循环与递归两种方法详解

小鹿同学

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

原创

本文详细介绍Python中单链表反转的两种核心实现方式：循环（迭代）与递归。通过ListNode类定义节点，分别演示了如何利用pre和cur指针在循环中逐步反转指向，以及如何在递归调用中处理头尾节点关系。代码包含完整的测试用例，输出结果验证了从1->2->3->4到4->3->2->1的正确反转过程，适用于Python初学者理解链表操作。

单链表的反转操作可以通过循环（迭代）或递归两种主要方式来实现。

1. 循环反转单链表

在循环方法中，我们需要维护两个指针：pre指向当前节点的前一个节点，cur指向当前正在处理的节点。每次迭代时，将cur的next指针指向pre，从而完成局部反转，随后移动指针继续处理后续节点。

具体实现代码如下：

class ListNode: 
  def __init__(self,x): 
    self.val=x; 
    self.next=None; 
 
def nonrecurse(head):       #循环的方法反转链表 
  if head is None or head.next is None: 
    return head; 
  pre=None; 
  cur=head; 
  h=head; 
  while cur: 
    h=cur; 
    tmp=cur.next; 
    cur.next=pre; 
    pre=cur; 
    cur=tmp; 
  return h; 
   
head=ListNode(1);  #测试代码 
p1=ListNode(2);   #建立链表1->2->3->4->None; 
p2=ListNode(3); 
p3=ListNode(4); 
head.next=p1; 
p1.next=p2; 
p2.next=p3; 
p=nonrecurse(head);  #输出链表 4->3->2->1->None 
while p: 
  print p.val; 
  p=p.next;

运行结果如下：

4 3 2 1 >>>

2. 递归实现单链表反转

class ListNode: 
  def __init__(self,x): 
    self.val=x; 
    self.next=None; 
 
   
def recurse(head,newhead):  #递归，head为原链表的头结点，newhead为反转后链表的头结点 
  if head is None: 
    return ; 
  if head.next is None: 
    newhead=head; 
  else : 
    newhead=recurse(head.next,newhead); 
    head.next.next=head; 
    head.next=None; 
  return newhead; 
   
head=ListNode(1);        #测试代码 
p1=ListNode(2);         # 建立链表1->2->3->4->None 
p2=ListNode(3); 
p3=ListNode(4); 
head.next=p1; 
p1.next=p2; 
p2.next=p3; 
newhead=None; 
p=recurse(head,newhead);      #输出链表4->3->2->1->None 
while p: 
  print p.val; 
  p=p.next;

递归方法的运行结果与上述循环方法一致。