LeetCode 热题 100 206. 反转链表

LeetCode 热题 100 | 206. 反转链表

大家好，今天我们来办理一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度，要求我们将一个单链表反转，并返回反转后的链表。下面我将详细讲解解题思路，并附上 Python 代码实现。

---

题目描述

给定单链表的头节点 head，反转链表，并返回反转后的链表。
示例：

1. 输入：head = [1,2,3,4,5]
2. 输出：[5,4,3,2,1]

复制代码

---

解题思路

反转链表的核心头脑是改变链表中节点的指向关系，将每个节点的 next 指针指向前一个节点。我们可以通过 迭代 或 递归 两种方法来实现。

---

方法 1：迭代法

核心头脑

• 利用三个指针：
  
  
  
  • prev：指向当前节点的前一个节点，初始为 None
    。
    
  • curr：指向当前节点，初始为 head。
    
  • next：指向当前节点的下一个节点。
    
  
  
• 遍历链表，逐个反转节点的指向。
  

步调

• 初始化 prev = None
  ，curr = head。
  
• 遍历链表：
  
  
  
  • 保存 curr 的下一个节点：next = curr.next。
    
  • 反转当前节点的指向：curr.next = prev。
    
  • 移动 prev 和 curr：prev = curr，curr = next。
    
  
  
• 遍历竣事后，prev 就是反转后的链表的头节点。
  

代码实现

1. class ListNode:
2.     def __init__(self, val=0, next=None
3. ):
4.         self.val = val
5.         self.next = next
7. def reverseList(head):
8.     prev = None
9.   # 前一个节点
10.     curr = head  # 当前节点
11.    
12.     while curr:
13.         next = curr.next  # 保存下一个节点
14.         curr.next = prev  # 反转当前节点的指向
15.         prev = curr  # 移动 prev
16.         curr = next  # 移动 curr
17.    
18.     return prev  # 返回反转后的头节点

复制代码

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。须要遍历链表一次。
  
• 空间复杂度：O(1)，只利用了常数个额外空间。
  

---

方法 2：递归法

核心头脑

• 递归地反转链表：
  
  
  
  • 递归到链表的最后一个节点，将其作为新的头节点。
    
  • 在回溯过程中，逐个反转节点的指向。
    
  
  

步调

• 递归停止条件：如果链表为空或只有一个节点，直接返回 head。
  
• 递归调用：反转 head.next 之后的链表。
  
• 反转当前节点的指向：head.next.next = head。
  
• 断开当前节点的指向：head.next = None
  。
  
• 返回新的头节点。
  

代码实现

1. class ListNode:
2.     def __init__(self, val=0, next=None
3. ):
4.         self.val = val
5.         self.next = next
7. def reverseList(head):
8.     # 递归终止条件
9.     if not head or not head.next:
10.         return head
11.    
12.     # 递归反转剩余链表
13.     new_head = reverseList(head.next)
14.    
15.     # 反转当前节点的指向
16.     head.next.next = head
17.     head.next = None
19.    
20.     # 返回新的头节点
21.     return new_head

复制代码

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。须要递归调用 n 次。
  
• 空间复杂度：O(n)，递归调用栈的深度为 n。
  

---

示例运行

示例 1

1. # 创建链表 1 -> 2 -> 3 -> 4 -> 5
2. head = ListNode(1)
3. head.next = ListNode(2)
4. head.next.next = ListNode(3)
5. head.next.next.next = ListNode(4)
6. head.next.next.next.next = ListNode(5)
8. # 反转链表
9. reversed_head = reverseList(head)
11. # 输出反转后的链表
12. while reversed_head:
13.     print(reversed_head.val, end=" -> ")
14.     reversed_head = reversed_head.next
15. print("None
16. ")

复制代码

输出：

1. 5 -> 4 -> 3 -> 2 -> 1 -> None

复制代码

示例 2

1. # 创建链表 1 -> 2
2. head = ListNode(1)
3. head.next = ListNode(2)
5. # 反转链表
6. reversed_head = reverseList(head)
8. # 输出反转后的链表
9. while reversed_head:
10.     print(reversed_head.val, end=" -> ")
11.     reversed_head = reversed_head.next
12. print("None
13. ")

复制代码

输出：

1. 2 -> 1 -> None

复制代码

示例 3

1. # 创建空链表
2. head = None
5. # 反转链表
6. reversed_head = reverseList(head)
8. # 输出反转后的链表
9. while reversed_head:
10.     print(reversed_head.val, end=" -> ")
11.     reversed_head = reversed_head.next
12. print("None
13. ")

复制代码

输出：

1. None

复制代码

---

总结

• 迭代法：通过遍历链表，逐个反转节点的指向，时间复杂度为 O(n)，空间复杂度为 O(1)。
  
• 递归法：通过递归调用反转链表，时间复杂度为 O(n)，空间复杂度为 O(n)。
  
• 两种方法都能高效地办理反转链表的问题，选择哪种方法取决于具体需求和场景。
  

希望这篇题解对你有帮助！如果另有其他问题，欢迎继承提问！
关注我，获取更多算法题解和编程技巧！

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。