作者介绍:10年大厂数据\经营分析经验,现任大厂数据部门负责人。
会一些的技术:数据分析、算法、SQL、大数据相关、python
欢迎加入社区:码上找工作
作者专栏每日更新:
备注说明:方便大家阅读,统一使用python,带必要注释,公众号 数据分析螺丝钉 一起打怪升级
本文详细讨论了链表反转的三种方法:迭代、全递归和局部递归,提供了代码实现,并比较了它们的效率和适用场景。
题目描述
反转从位置 m
到 n
的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m
≤ n
≤ 链表长度。
输入格式
- head:链表的头节点。
- m:开始反转的位置。
- n:结束反转的位置。
输出格式
- 返回反转部分后的链表头节点。
示例
示例 1
输入: 1->2->3->4->5->NULL, m = 2, n = 4 输出: 1->4->3->2->5->NULL
方法一:迭代
解题步骤
- 定位节点:找到第
m-1
个节点(反转的前一个节点)。 - 反转区间:迭代反转从
m
到n
的节点。
完整的规范代码
class ListNode: def __init__(self, x): self.val = x self.next = None def reverseBetween(head, m, n): """ 一次扫描反转链表的部分区间 :param head: ListNode, 链表的头节点 :param m: int, 开始反转的位置 :param n: int, 结束反转的位置 :return: ListNode, 反转部分后的链表头节点 """ if not head: return None # 创建一个哑节点,简化边界问题处理 dummy = ListNode(0) dummy.next = head pre = dummy # 第一部分:找到第 m-1 个节点 for _ in range(m - 1): pre = pre.next # 反转的起始节点 start = pre.next then = start.next # 第二部分:反转从 m 到 n 的节点 for _ in range(n - m): start.next = then.next then.next = pre.next pre.next = then then = start.next return dummy.next # 示例调用 node1 = ListNode(1) node2 = ListNode(2) node3 = ListNode(3) node4 = ListNode(4) node5 = ListNode(5) node1.next = node2 node2.next = node3 node3.next = node4 node4.next = node5 result = reverseBetween(node1, 2, 4)
算法分析
- 时间复杂度:(O(n)),其中
n
是链表的长度,需要一趟遍历找到反转的起始位置。 - 空间复杂度:(O(1)),使用了有限的几个额外变量。
方法二:递归
解题步骤
- 递归反转:利用递归在到达第
m
个节点时开始反转,直到第n
个节点。 - 连接反转部分:递归返回时,重新连接已反转部分与未反转部分。
完整的规范代码
def reverseBetween(head, m, n): """ 使用递归反转链表的部分区间 :param head: ListNode, 链表的头节点 :param m: int, 开始反转的位置 :param n: int, 结束反转的位置 :return: ListNode, 反转部分后的链表头节点 """ global successor # 后继节点,即反转部分之后的第一个节点 if m == 1: return reverseN(head, n) head.next = reverseBetween(head.next, m - 1, n - 1) return head def reverseN(head, n): if n == 1: successor = head.next return head last = reverseN(head.next, n - 1) head.next.next = head head.next = successor return last # 示例调用省略,与方法一类似,使用 ListNode 定义链表并调用 reverseBetween 函数
算法分析
- 时间复杂度:(O(n)),递归过程中节点只被访问一次。
- 空间复杂度:(O(n)),递归深度最大为
n
,在最坏情况下为链表的长度。
方法三:反转前 n
个节点的递归
解题步骤
- 局部反转:定义一个递归函数反转链表的前
n
个节点。 - 调整指针:在递归中调整指针连接,完成局部反转。
完整的规范代码
def reverseN(head, n): """ 递归反转链表的前 n 个节点 :param head: ListNode, 链表的头节点 :param n: int, 需要反转的节点数 :return: ListNode, 反转后的链表头节点 """ if n == 1: successor = head.next # 后继节点,即未反转部分的头节点 return head last = reverseN(head.next, n - 1) head.next.next = head head.next = successor return last # 示例调用省略,与方法二类似,使用 ListNode 定义链表并调用 reverseN 函数
不同算法的优劣势对比
特征 | 方法一:迭代 | 方法二:递归 | 方法三:局部反转递归 |
时间复杂度 | (O(n)) | (O(n)) | (O(n)) |
空间复杂度 | (O(1)) | (O(n)) | (O(n)) |
优势 | 直接且高效,无需额外空间 | 代码简洁,直观易懂 | 适用于需要反转链表前部分的场景 |
劣势 | 需要处理多个指针,逻辑稍复杂 | 空间复杂度较高,递归深度大时可能栈溢出 | 使用场景有限,递归深度依然是问题 |
应用示例
链表的部分反转在许多实际应用中都非常有用,例如在编辑软件中撤销操作的实现、操作系统的任务调度等。这些算法为处理类似问题提供了有效的解决方案。
欢迎关注微信公众号 数据分析螺丝钉