[Leetcode 92] 反转链表II

type
status
date
summary
tags
category
icon
password
featured
freq
difficulty
给出单链表的头指针head和两个整数leftright,其中left <= right
反转从位置left到位置right之间的链表节点,返回反转后的链表
 
示例 1:
notion image
 
示例 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],回来后拼上即可。
  • 每递归一层,就把 leftright 都减一。
  • 直到递归到 left == 1,就变成了“反转前 n = right 个节点”的问题。
复杂度
  • 时间:O(n)(递归深度与区间长度相关)
  • 空间:O(n)(递归栈)
上一篇
[Leetcode 88] 合并两个有序数组
下一篇
[Leetcode 101] 对称二叉树