92.反转链表 II

题目:反转链表 II

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

• 示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

• 示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

• 提示：

链表中节点数目为 n
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

思路

你可以通过以下步骤来反转单链表中从位置 left 到 right 的节点。这里的实现使用了多指针技术来完成节点的局部反转。注意，我们要确保在操作时保留链表的其他部分的完整性。

实现步骤

1. 找到 left 的前一个节点：通过遍历找到第 left-1 个节点，它指向要反转部分的第一个节点。我们将这个节点命名为 prev。

2. 反转指定区间的节点：通过指针操作，将第 left 个节点到第 right 个节点之间的链表反转。

   假设链表为：1 -> 2 -> 3 -> 4 -> 5，并且要反转链表中间部分的节点，比如从节点 2 到节点 4 之间的节点，即left = 2, right = 4。

   初始状态:

   • prev指向1（即left前一个节点）
   • start指向2（即要反转部分的第一个节点）
   • then指向3（即start.next）

   1 (prev) -> 2 (start) -> 3 (then) -> 4 -> 5

   第一步:

   • start.next = then.next，将2的next指向4。
   • then.next = prev.next，将3的next指向2。
   • prev.next = then，将1的next指向3。
   • then = start.next，更新then为4。

   1 (prev) -> 3 (then) -> 2 (start) -> 4 -> 5

   第二步:

   • start.next = then.next，将2的next指向5。
   • then.next = prev.next，将4的next指向3。
   • prev.next = then，将1的next指向4。
   • then = start.next，更新then为5。

   1 (prev) -> 4 -> 3 -> 2 (start) -> 5

   最终状态:
   完成反转，链表部分节点2到4已经成功反转：

   1 -> 4 -> 3 -> 2 -> 5

3. 返回新链表的头节点：最后返回 result.next 作为新的头节点。

• 时间复杂度:O(n)
• 空间复杂度:O(1)

代码

public ListNode reverseBetween(ListNode head, int left, int right) {
    // 创建虚拟头节点以简化操作
    ListNode result = new ListNode(0);
    result.next = head;
    ListNode prev = result;
    // 找到left前的节点
    for (int i = 1; i < left; i++) {
        prev = prev.next;
    }
    // 开始反转链表
    ListNode start = prev.next;
    ListNode then = start.next;
    for (int i = 0; i < right - left; i++) {
        start.next = then.next;
        then.next = prev.next;
        prev.next = then;
        then = start.next;
    }
    return result.next;
}