type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给出单链表的头指针
head和两个整数left和right,其中left <= right。反转从位置
left到位置right之间的链表节点,返回反转后的链表。示例 1:

示例 2:
解法一:原地交换(推荐)
把
[left, right] 链表想象成一个操场,入口是 pre,也就是左边界前一个节点。操场里的人不离开,只是不断调整站位。每次把第二个人拉到最前面,重新站队。操场内的人顺序逐渐反转。比如:
原始顺序:1 → 2 → 3 → 4
第一次调整:把 2 插到 1 前面 → 2 → 1 → 3 → 4
第二次调整:把 3 插到 2 前面 → 3 → 2 → 1 → 4
第三次调整:把 4 插到 3 前面 → 4 → 3 → 2 → 1
重复
right-left 次,整段就倒过来了。也就是每次把
cur.next 摘下并头插到 pre 的后面,pre 后面那段会逐渐形成“反转结果”。由于操作都只在
[left, right] 内进行,且我们一直维护 tail.next(即 cur.next)不丢失,指针安全而且线性扫描就能完事。好处是我们不需要额外数组/栈,不需要先裁下子链再接回,指针一直在同一个区域里滚动,非常紧凑。
复杂度
- 时间:
O(n)(一趟扫描完成,核心循环做了right - left次搬运)
- 空间:
O(1)(原地)
解法二:反转子链再拼回
把
[left, right] 这一段裁出来,当它是一个独立链表,直接用“206 题标准反转”把它反过来,最后把“前半 + 反转段 + 后半”重新接起来。 反转段落和全链反转是一样的操作,只是额外多了“找到四个连接点”:
reversePre(左段的尾)、reverseHead(反转前的段头)、
reverseTail(反转后的段头)、reverseNext(右段的头)。
重新连边就是把这四个点正确拼起来。
与解法一一样,也是一次线性遍历,只不过形式上分“定位 + 反转 + 拼接”三个阶段。
复杂度
- 时间:
O(n)
- 空间:
O(1)
方法三:递归
如果
left == 1,就从链表头开始反转,目标是反转前 right 个节点。- 子问题:如何递归地反转链表的前
n个节点,并且保留好 “第n+1个节点”的指针,方便收尾接回去。
如果
left > 1,先跳过前 left - 1 个节点,递归去反转子链的 [left-1, right-1],回来后拼上即可。- 每递归一层,就把
left和right都减一。
- 直到递归到
left == 1,就变成了“反转前n = right个节点”的问题。
复杂度
- 时间:
O(n)(递归深度与区间长度相关)
- 空间:
O(n)(递归栈)
- Author:Fan Luo
- URL:https://fanluo.me/article/leetcode-92-反转链表ii
- Copyright:All articles in this blog adopt BY-NC-SA agreement. Please indicate the source!
上一篇
[Leetcode 88] 合并两个有序数组
下一篇
[Leetcode 101] 对称二叉树