力扣链表
206. 反转链表
206. 反转链表
https://leetcode.cn/problems/reverse-linked-list/
题目
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
示例
示例 1： 输入：head = [1,2,3,4,5] 输出：[5,4,3,2,1]
示例 2： 输入：head = [1,2] 输出：[2,1]
示例 3： 输入：head = [] 输出：[]
提示
- 链表中节点的数目范围是 [0, 5000]
- -5000 <= Node.val <= 5000
思路一（迭代法 / 双指针法）
使用双指针逐步反转链表指向：
- 定义
prev和cur两个指针，初始prev = None，cur = head； - 遍历链表时，保存
cur.next，然后将cur.next指向prev； - 依次向后移动
prev和cur，直到cur为空； - 遍历结束后，
prev即为反转后的新头节点。
该思路时间复杂度为 O(n)，空间复杂度为 O(1)。
解法一（迭代法）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
prev = None
cur = head
while cur:
temp = cur.next # 保存下一个节点
cur.next = prev # 反转当前节点指向
prev = cur # prev 移动到当前节点
cur = temp # cur 移动到下一个节点
return prev解释一（迭代法代码解释）
| 代码片段 | 作用与原因 |
|---|---|
prev = None; cur = head | 初始化：prev 指向 None（反转后尾节点指向 None），cur 指向链表头 |
temp = cur.next | 保存 cur 的下一个节点，因为修改 cur.next 后会丢失原始链表 |
cur.next = prev | 核心反转操作：将当前节点的 next 指向 prev，实现反转 |
prev = cur | prev 移动到当前节点位置 |
cur = temp | cur 移动到下一个节点，继续遍历 |
return prev | 遍历结束后，prev 指向原链表最后一个节点，即新链表头节点 |
思路二（递归法）
利用递归"自底向上"的思想，从链表尾部开始反转：
- 递归终止条件：链表为空或只有一个节点时，无需反转，直接返回；
- 递归处理子问题：先递归到链表末尾，得到反转后的子链表头节点；
- 反转当前节点：让当前节点的下一个节点的 next 指向当前节点，同时将当前节点的 next 置为 None。
该思路时间复杂度为 O(n)，空间复杂度为 O(n)（递归调用栈）。
解法二（递归法）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
if not head or not head.next:
return head
# 递归到链表末尾，返回反转后的新头节点
new_head = self.reverseList(head.next)
# 反转当前节点的指向
head.next.next = head
head.next = None
return new_head解释二（递归法代码解释）
| 代码片段 | 作用与原因 |
|---|---|
if not head or not head.next: return head | 递归终止条件：空链表或单节点无需反转，直接返回 |
new_head = self.reverseList(head.next) | 递归调用，深入到链表末尾，最后返回反转后的新头节点 |
head.next.next = head | 将下一个节点的 next 指向当前节点，实现反转 |
head.next = None | 当前节点的 next 置为 None，避免形成环 |
return new_head | 将反转后的新头节点逐层回传 |
思路三（头插法）
创建一个新链表，通过"头插"方式逐步将原链表节点插入到新链表头部：
- 创建新链表头
new_head = None； - 遍历原链表，将每个节点插入到新链表头部；
- 遍历结束后，新链表即为反转后的链表。
该思路时间复杂度为 O(n)，空间复杂度为 O(1)。
解法三（头插法）
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
new_head = None
cur = head
while cur:
temp = cur.next # 保存下一个节点
cur.next = new_head # 将当前节点插入新链表头部
new_head = cur # 更新新链表头
cur = temp # 移动到原链表的下一个节点
return new_head