作者介绍：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)) |
| 优势 | 直接且高效，无需额外空间 | 代码简洁，直观易懂 | 适用于需要反转链表前部分的场景 |
| 劣势 | 需要处理多个指针，逻辑稍复杂 | 空间复杂度较高，递归深度大时可能栈溢出 | 使用场景有限，递归深度依然是问题 |
应用示例
链表的部分反转在许多实际应用中都非常有用，例如在编辑软件中撤销操作的实现、操作系统的任务调度等。这些算法为处理类似问题提供了有效的解决方案。
欢迎关注微信公众号 数据分析螺丝钉
