外链网站有哪些,设计制造中国第一架飞机的人是,玛卡h5制作官网,软件定制开发费用多少云鲸互创团队LeetCode 热题 100 | 206. 反转链表
大家好#xff0c;今天我们来解决一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度#xff0c;要求我们将一个单链表反转#xff0c;并返回反转后的链表。下面我将详细讲解解题思路#xff0c;并附上 Python 代码实…LeetCode 热题 100 | 206. 反转链表
大家好今天我们来解决一道经典的算法题——反转链表。这道题在 LeetCode 上被标记为简单难度要求我们将一个单链表反转并返回反转后的链表。下面我将详细讲解解题思路并附上 Python 代码实现。 题目描述
给定单链表的头节点 head反转链表并返回反转后的链表。
示例
输入head [1,2,3,4,5]
输出[5,4,3,2,1]解题思路
反转链表的核心思想是改变链表中节点的指向关系将每个节点的 next 指针指向前一个节点。我们可以通过 迭代 或 递归 两种方法来实现。 方法 1迭代法
核心思想
使用三个指针 prev指向当前节点的前一个节点初始为 None。curr指向当前节点初始为 head。next指向当前节点的下一个节点。 遍历链表逐个反转节点的指向。
步骤
初始化 prev Nonecurr head。遍历链表 保存 curr 的下一个节点next curr.next。反转当前节点的指向curr.next prev。移动 prev 和 currprev currcurr next。 遍历结束后prev 就是反转后的链表的头节点。
代码实现
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef reverseList(head):prev None # 前一个节点curr head # 当前节点while curr:next curr.next # 保存下一个节点curr.next prev # 反转当前节点的指向prev curr # 移动 prevcurr next # 移动 currreturn prev # 返回反转后的头节点复杂度分析
时间复杂度O(n)其中 n 是链表的长度。需要遍历链表一次。空间复杂度O(1)只使用了常数个额外空间。 方法 2递归法
核心思想
递归地反转链表 递归到链表的最后一个节点将其作为新的头节点。在回溯过程中逐个反转节点的指向。
步骤
递归终止条件如果链表为空或只有一个节点直接返回 head。递归调用反转 head.next 之后的链表。反转当前节点的指向head.next.next head。断开当前节点的指向head.next None。返回新的头节点。
代码实现
class ListNode:def __init__(self, val0, nextNone):self.val valself.next nextdef reverseList(head):# 递归终止条件if not head or not head.next:return head# 递归反转剩余链表new_head reverseList(head.next)# 反转当前节点的指向head.next.next headhead.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)。两种方法都能高效地解决反转链表的问题选择哪种方法取决于具体需求和场景。
希望这篇题解对你有帮助如果还有其他问题欢迎继续提问
关注我获取更多算法题解和编程技巧
