Python实现链表翻转：两种核心算法解析

陆景行

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

原创

本文详细解析Python中链表翻转的两种实现方式。首先介绍基于新建空节点的迭代法，通过遍历节点并重新指向头节点实现翻转；其次讲解难度稍高的原地翻转法，利用摘链与重连技巧在空间复杂度O(1)下完成操作。文章包含完整代码示例及步骤说明，适合准备算法面试的开发者参考。

实现链表翻转操作

示例场景：给定一个单向链表 1->2->3->null，翻转后的结果应为 3->2->1->null

一种直观且易于理解的方案是采用“摘除法”。具体思路是初始化一个空节点作为新链表的头部，随后遍历原链表，将遍历到的每个节点依次指向新链表的头节点，从而逐步构建翻转后的链表。

以示例数据为例，具体执行步骤如下：

1. 初始化空节点：None 2. 处理节点 1，使其指向 None：1->None 3. 处理节点 2，使其指向节点 1：2->1->None 4. 处理节点 3，使其指向节点 2：3->2->1->None

基于上述逻辑的代码实现如下：

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  temp = None 
  while head: 
   cur = head.next 
   head.next = temp 
   temp = head 
   head = cur 
  return temp 
  # write your code here

此外，还存在一种复杂度稍高但空间效率更优的解法。该方法通过对链表节点进行依次摘链和重新链接，实现原地翻转（In-place Reversal）：

""" 
Definition of ListNode 
 
class ListNode(object): 
 
 def __init__(self, val, next=None): 
  self.val = val 
  self.next = next 
""" 
class Solution: 
 """ 
 @param head: The first node of the linked list. 
 @return: You should return the head of the reversed linked list. 
     Reverse it in-place. 
 """ 
 def reverse(self, head): 
  if head is None: 
   return head 
  dummy = ListNode(-1) 
  dummy.next = head 
  pre, cur = head, head.next 
  while cur: 
   temp = cur 
   # 把摘链的地方连起来 
   pre.next = cur.next 
   cur = pre.next 
   temp.next = dummy.next 
   dummy.next = temp 
  return dummy.next 
  # write your code here

在实施摘链操作时，务必注意将摘除节点后的断点重新连接，以确保链表结构的完整性。

感谢阅读，希望本文内容能对大家有所帮助，感谢各位对本站的支持！