92.反转链表2

LeetCode 原题链接 题目

代码实现

方案一

实现思路

方案一先找到反转区间的前后边界，再完成区间反转：

  1. 创建 dummy 节点指向 head，让 left = 1 时也能找到区间前一个节点。
  2. 让 leftNode 从 dummy 出发，移动 left - 1 次，定位到反转区间前一个节点。
  3. 让 rightNode 从 dummy 出发，移动 right 次，定位到反转区间最后一个节点。
  4. 记录 rightNode.next，它是反转区间后面的第一个节点，并将它作为 prev 的初始值。
  5. 从 leftNode.next 开始反转固定的 right - left + 1 个节点。反转结束后，prev 指向新的区间头，原来的区间头已经成为新的区间尾，并自动连接到区间后继节点。
  6. 将 leftNode.next 连接到 prev，完成整个链表的连接。

例如链表为 1 → 2 → 3 → 4 → 5，left = 2，right = 4：

1 → [2 → 3 → 4] → 5
      ↓
1 → [4 → 3 → 2] → 5

代码实现

var reverseBetween = function (head, left, right) {
  if (head === null) return head;

  const dummy = new ListNode(0, head);

  let leftNode = dummy;
  for (let i = 0; i < left - 1; i++) {
    leftNode = leftNode.next;
  }
  let rightNode = dummy;
  for (let j = 0; j < right; j++) {
    rightNode = rightNode.next;
  }

  // prev 从区间后继节点开始，反转后原来的区间头会连接到它
  let prev = rightNode.next;
  let cur = leftNode.next;
  for (let k = 0; k < right - left + 1; k++) {
    let temp = cur.next;
    cur.next = prev;
    prev = cur;
    cur = temp;
  }

  // prev 是反转后的区间头
  leftNode.next = prev;

  return dummy.next;
};

方案二

实现思路

方案二不提前寻找 rightNode，只定位区间前一个节点，然后根据区间长度直接反转：

  1. 创建 dummy 节点指向 head，统一处理反转头节点的情况。
  2. 让 beforeLeft 从 dummy 出发，移动到第 left - 1 个位置，找到反转区间前一个节点。
  3. 保存反转区间头 leftNode，并使用 prev、cur 反转 right - left + 1 个节点。
  4. 反转结束后，prev 是新的区间头，cur 是区间后继节点，原来的 leftNode 是新的区间尾。
  5. 将 beforeLeft.next 指向 prev，将 leftNode.next 指向 cur，把反转区间接回原链表。

代码实现

var reverseBetween = function (head, left, right) {
  if (head === null) return head;

  const dummy = new ListNode(0, head);

  // 1. 找到反转区间前一个节点
  let beforeLeft = dummy;

  for (let i = 1; i < left; i++) {
    beforeLeft = beforeLeft.next;
  }

  // 2. 开始反转 [left, right]
  const leftNode = beforeLeft.next;
  let prev = null;
  let cur = leftNode;

  for (let i = 0; i < right - left + 1; i++) {
    const next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
  }

  // 3. 接回链表：prev 是反转后的区间头，cur 是区间后继节点
  beforeLeft.next = prev;
  leftNode.next = cur;

  return dummy.next;
};

复杂度分析

  • 时间复杂度：O(n)，需要遍历到反转区间，并反转区间内的节点。
  • 空间复杂度：O(1)，只使用了常数个指针。

边界情况

  • head 为空时，直接返回空链表。
  • left === right 时，区间只有一个节点，链表不变。
  • left === 1 时，dummy 节点可以代替区间前一个节点，避免单独处理头节点。
  • right 等于链表长度时，区间后继节点为 null，反转后的区间尾连接到 null。