区间反转链表的实现与解析 - 详细步骤与代码示例

区间反转链表是一个常见的算法问题，通常用于面试和实际开发中。给定一个单链表和两个整数 left 和 right，要求反转从位置 left 到 right 的链表节点。以下是实现这一功能的详细步骤和代码示例。

问题描述

给定一个单链表和两个整数 left 和 right，反转从位置 left 到 right 的链表节点。要求只进行一次遍历。

示例

输入: 1 -> 2 -> 3 -> 4 -> 5, left = 2, right = 4
输出: 1 -> 4 -> 3 -> 2 -> 5

解决思路

1. 定位反转区间的前一个节点：首先找到 left 位置的前一个节点 prev，以便在反转后能够正确连接。
2. 反转区间内的节点：从 left 到 right 的节点进行反转。
3. 重新连接链表：将反转后的区间重新连接到原链表中。

代码实现

以下是使用 JavaScript 实现的代码：

function reverseBetween(head, left, right) {
    if (!head || left === right) return head;

    // 创建一个虚拟节点，简化边界条件处理
    const dummy = new ListNode(0);
    dummy.next = head;
    let prev = dummy;

    // 移动到 left 的前一个节点
    for (let i = 0; i < left - 1; i++) {
        prev = prev.next;
    }

    // 开始反转
    let start = prev.next; // 反转区间的第一个节点
    let then = start.next; // 将要移动的节点

    for (let i = 0; i < right - left; i++) {
        start.next = then.next;
        then.next = prev.next;
        prev.next = then;
        then = start.next;
    }

    return dummy.next;
}

// 链表节点定义
class ListNode {
    constructor(val, next = null) {
        this.val = val;
        this.next = next;
    }
}

// 示例用法
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
head.next.next.next.next = new ListNode(5);

const result = reverseBetween(head, 2, 4);

// 打印结果
let current = result;
while (current) {
    console.log(current.val);
    current = current.next;
}

代码解释

1. 虚拟节点：创建一个虚拟节点 dummy，并将其 next 指向链表的头节点。这样可以简化边界条件的处理，特别是当 left 为 1 时。
2. 定位 prev：通过循环将 prev 移动到 left 位置的前一个节点。
3. 反转区间：使用 start 和 then 两个指针来反转区间内的节点。start 始终指向反转区间的第一个节点，then 指向 start 的下一个节点。通过交换 then 和 prev.next 的位置，逐步将 then 移动到 prev.next 的位置，实现反转。
4. 返回结果：最终返回 dummy.next，即反转后的链表头节点。

复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。我们只需要遍历链表一次。
• 空间复杂度：O(1)，只使用了常数个额外的指针。

总结

区间反转链表是一个经典的链表操作问题，通过使用虚拟节点和双指针技巧，可以高效地解决这个问题。理解并掌握这种技巧对于处理链表相关的问题非常有帮助。