单链表反转是数据结构与算法中的经典问题，它不仅考察对链表结构的理解，也考验编程思维和技巧。本文将带你从基础实现到高级应用，全面掌握单链表反转。
1. 理解单链表
在深入反转算法之前，我们先回顾单链表的基本结构：
1class ListNode: 2 def __init__(self, val=0, next=None): 3 self.val = val 4 self.next = next 5
单链表的特点是每个节点包含数据和指向下一个节点的指针，只能单向遍历。
2. 基础反转方法
2.1 迭代法（最常用）
核心思想：逐个改变节点指向，从前往后反转。
1def reverse_list_iterative(head): 2 prev = None 3 current = head 4 5 while current: 6 # 保存下一个节点 7 next_temp = current.next 8 # 反转指针 9 current.next = prev 10 # 移动指针 11 prev = current 12 current = next_temp 13 14 return prev # 新的头节点 15
执行过程可视化：
1原链表: 1 → 2 → 3 → 4 → 5 → None 2 3步骤1: None ← 1 2 → 3 → 4 → 5 → None 4步骤2: None ← 1 ← 2 3 → 4 → 5 → None 5步骤3: None ← 1 ← 2 ← 3 4 → 5 → None 6... 7结果: None ← 1 ← 2 ← 3 ← 4 ← 5 8
2.2 递归法
核心思想：通过递归到达链表末端，然后从后往前反转。
1def reverse_list_recursive(head): 2 # 递归终止条件 3 if not head or not head.next: 4 return head 5 6 # 递归到最后一个节点 7 new_head = reverse_list_recursive(head.next) 8 9 # 反转指针 10 head.next.next = head 11 head.next = None 12 13 return new_head 14
递归过程分析：
1reverse(1) 2 reverse(2) 3 reverse(3) 4 reverse(4) 5 reverse(5) → 返回5 6 5.next = 4, 4.next = None 7 5.next = 3, 3.next = None 8 5.next = 2, 2.next = None 95.next = 1, 1.next = None 10
3. 进阶反转技巧
3.1 反转部分链表
反转链表中从位置 m 到 n 的部分：
1def reverse_between(head, m, n): 2 if not head or m == n: 3 return head 4 5 dummy = ListNode(0) 6 dummy.next = head 7 prev = dummy 8 9 # 移动到第m-1个节点 10 for _ in range(m - 1): 11 prev = prev.next 12 13 # 开始反转 14 current = prev.next 15 for _ in range(n - m): 16 temp = current.next 17 current.next = temp.next 18 temp.next = prev.next 19 prev.next = temp 20 21 return dummy.next 22
3.2 K个一组反转链表
每 k 个节点一组进行反转，不足 k 的保持原样：
1def reverse_k_group(head, k): 2 def reverse_sublist(start, end): 3 prev, curr = None, start 4 while curr != end: 5 next_temp = curr.next 6 curr.next = prev 7 prev = curr 8 curr = next_temp 9 return prev 10 11 # 检查是否有k个节点 12 node = head 13 for _ in range(k): 14 if not node: 15 return head 16 node = node.next 17 18 # 反转前k个节点 19 new_head = reverse_sublist(head, node) 20 # 递归处理剩余部分 21 head.next = reverse_k_group(node, k) 22 23 return new_head 24
3.3 交替反转
第一个k个节点反转，下一个k个节点保持，如此交替：
1def reverse_alternate_k_nodes(head, k): 2 if not head or k <= 1: 3 return head 4 5 current = head 6 prev = None 7 reverse = True 8 9 while current: 10 if reverse: 11 # 反转k个节点 12 section_start = current 13 section_prev = None 14 count = 0 15 16 # 检查是否有足够的节点 17 temp = current 18 for _ in range(k): 19 if not temp: 20 break 21 temp = temp.next 22 23 # 反转当前段 24 while current and count < k: 25 next_temp = current.next 26 current.next = section_prev 27 section_prev = current 28 current = next_temp 29 count += 1 30 31 # 连接已反转部分 32 if prev: 33 prev.next = section_prev 34 else: 35 head = section_prev 36 37 section_start.next = current 38 prev = section_start 39 reverse = False 40 else: 41 # 跳过k个节点 42 count = 0 43 while current and count < k: 44 prev = current 45 current = current.next 46 count += 1 47 reverse = True 48 49 return head 50
4. 特殊场景反转
4.1 反转链表的前N个节点
1def reverse_first_n(head, n): 2 successor = None 3 4 def reverse_n(node, count): 5 nonlocal successor 6 if count == 1: 7 successor = node.next 8 return node 9 10 last = reverse_n(node.next, count - 1) 11 node.next.next = node 12 node.next = successor 13 return last 14 15 return reverse_n(head, n) 16
4.2 从末尾开始反转
1def reverse_from_end(head, k): 2 # 先找到总长度 3 length = 0 4 current = head 5 while current: 6 length += 1 7 current = current.next 8 9 # 转换为从头开始的位置 10 m = length - k + 1 11 return reverse_between(head, m, length) 12
5. 性能分析与比较
| 方法 | 时间复杂度 | 空间复杂度 | 适用场景 |
|---|---|---|---|
| 迭代法 | O(n) | O(1) | 通用，最常用 |
| 递归法 | O(n) | O(n) | 代码简洁，栈深度受限 |
| 部分反转 | O(n) | O(1) | 局部操作 |
| K组反转 | O(n) | O(n/k) | 批量处理 |
6. 实战技巧与注意事项
6.1 边界情况处理
- 空链表
- 单节点链表
- 反转位置超出范围
- k值大于链表长度
6.2 调试技巧
1def print_list(head): 2 """打印链表用于调试""" 3 result = [] 4 current = head 5 while current: 6 result.append(str(current.val)) 7 current = current.next 8 print(" → ".join(result) + " → None") 9
6.3 常见错误
- 忘记处理头节点的更新
- 指针丢失（在改变next前未保存）
- 循环链表的形成
- 边界条件处理不完整
7. 综合练习
题目：给定链表 1→2→3→4→5→6→7，要求实现：
- 完全反转
- 反转2-5位置
- 每3个一组反转
- 交替每2个节点反转
1# 测试用例 2def create_sample_list(): 3 nodes = [ListNode(i) for i in range(1, 8)] 4 for i in range(len(nodes)-1): 5 nodes[i].next = nodes[i+1] 6 return nodes[0] 7 8# 测试各种反转方法 9head = create_sample_list() 10print("原链表:") 11print_list(head) 12 13print("\n完全反转:") 14print_list(reverse_list_iterative(create_sample_list())) 15 16print("\n反转位置2-5:") 17print_list(reverse_between(create_sample_list(), 2, 5)) 18 19print("\n每3个一组反转:") 20print_list(reverse_k_group(create_sample_list(), 3)) 21
总结
单链表反转是算法学习中的重要里程碑。掌握从基础到进阶的各种反转技巧，不仅能够解决链表相关问题，更能培养严谨的编程思维和指针操作能力。建议通过大量练习来熟练掌握这些技巧，并理解每种方法适用的场景。
记住：多画图理解指针变化，多写代码加深印象，这是掌握链表问题的关键！
《单链表反转：从基础到进阶的完整指南》 是转载文章，点击查看原文。
