LeetCode 热题 100 206. 反转链表
LeetCode 热题 100 | 206. 反转链表大家好，今天我们来办理一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度，要求我们将一个单链表反转，并返回反转后的链表。下面我将详细讲解解题思路，并附上 Python 代码实现。
题目描述
给定单链表的头节点 head，反转链表，并返回反转后的链表。
示例：
输入：head =
输出：
解题思路
反转链表的核心头脑是改变链表中节点的指向关系，将每个节点的 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 就是反转后的链表的头节点。
代码实现
class ListNode:
def __init__(self, val=0, next=None
):
self.val = val
self.next = next
def reverseList(head):
prev = None
# 前一个节点
curr = head# 当前节点
while curr:
next = curr.next# 保存下一个节点
curr.next = prev# 反转当前节点的指向
prev = curr# 移动 prev
curr = next# 移动 curr
return prev# 返回反转后的头节点
复杂度分析
[*]时间复杂度：O(n)，其中 n 是链表的长度。须要遍历链表一次。
[*]空间复杂度：O(1)，只利用了常数个额外空间。
方法 2：递归法
核心头脑
[*]递归地反转链表：
[*]递归到链表的最后一个节点，将其作为新的头节点。
[*]在回溯过程中，逐个反转节点的指向。
步调
[*]递归停止条件：如果链表为空或只有一个节点，直接返回 head。
[*]递归调用：反转 head.next 之后的链表。
[*]反转当前节点的指向：head.next.next = head。
[*]断开当前节点的指向：head.next = None
。
[*]返回新的头节点。
代码实现
class ListNode:
def __init__(self, val=0, next=None
):
self.val = val
self.next = next
def reverseList(head):
# 递归终止条件
if not head or not head.next:
return head
# 递归反转剩余链表
new_head = reverseList(head.next)
# 反转当前节点的指向
head.next.next = head
head.next = None
# 返回新的头节点
return new_head
复杂度分析
[*]时间复杂度：O(n)，其中 n 是链表的长度。须要递归调用 n 次。
[*]空间复杂度：O(n)，递归调用栈的深度为 n。
示例运行
示例 1
# 创建链表 1 -> 2 -> 3 -> 4 -> 5
head = ListNode(1)
head.next = ListNode(2)
head.next.next = ListNode(3)
head.next.next.next = ListNode(4)
head.next.next.next.next = ListNode(5)
# 反转链表
reversed_head = reverseList(head)
# 输出反转后的链表
while reversed_head:
print(reversed_head.val, end=" -> ")
reversed_head = reversed_head.next
print("None
")
输出：
5 -> 4 -> 3 -> 2 -> 1 -> None
示例 2
# 创建链表 1 -> 2
head = ListNode(1)
head.next = ListNode(2)
# 反转链表
reversed_head = reverseList(head)
# 输出反转后的链表
while reversed_head:
print(reversed_head.val, end=" -> ")
reversed_head = reversed_head.next
print("None
")
输出：
2 -> 1 -> None
示例 3
# 创建空链表
head = None
# 反转链表
reversed_head = reverseList(head)
# 输出反转后的链表
while reversed_head:
print(reversed_head.val, end=" -> ")
reversed_head = reversed_head.next
print("None
")
输出：
None
总结
[*]迭代法：通过遍历链表，逐个反转节点的指向，时间复杂度为 O(n)，空间复杂度为 O(1)。
[*]递归法：通过递归调用反转链表，时间复杂度为 O(n)，空间复杂度为 O(n)。
[*]两种方法都能高效地办理反转链表的问题，选择哪种方法取决于具体需求和场景。
希望这篇题解对你有帮助！如果另有其他问题，欢迎继承提问！
关注我，获取更多算法题解和编程技巧！
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]