题解 | #链表内指定区间反转#

链表内指定区间反转

任务

我们需要把一条项链上的某些珠子顺序反过来。比如，有这么一串珠子：1 → 2 → 3 → 4 → 5，我们想要把从第二个珠子到第四个珠子的位置反过来，结果应该是：1 → 4 → 3 → 2 → 5。

解决办法

1. 假设一个“假头”珠子

想象一下，我们在项链的最前面加了一个“假头”珠子，这样做的目的是为了让我们的工作更容易一些。这个“假头”珠子不真正存在，只是为了帮助我们找到正确的珠子。

ListNode dummy = new ListNode(0);
dummy.next = head;

2. 找到要反转的第一个珠子前面的那个珠子

我们需要找到第一个要反转的珠子（也就是第 m 个珠子）前面的一个珠子。比如，如果我们想从第二个珠子开始反转，那我们就要找到第一个珠子。

ListNode prev = dummy;
for (int i = 1; i < m; i++) {
    prev = prev.next; // 往前走一步
}

3. 一步一步地反转珠子

现在我们找到了第一个要反转的珠子前面的那个珠子，接下来我们要做的是把从 m 到 n 的珠子顺序反过来。我们可以想象一下，就像你在玩“翻花绳”的游戏一样，每次把一个珠子移到正确的位置。

ListNode current = prev.next; // 当前珠子为要反转的第一个珠子
for (int i = 0; i < n - m; i++) {
    ListNode temp = current.next; // 下一个要反转的珠子
    current.next = temp.next; // 把当前珠子和下一个珠子分开
    temp.next = prev.next; // 把下一个珠子插到 prev 后面
    prev.next = temp; // 把下一个珠子变成当前珠子
}

举例说明

假设我们有这样一串珠子：1 → 2 → 3 → 4 → 5，并且我们要从第二个珠子开始，到第四个珠子结束反转。

1. 初始化：
1. 我们加一个“假头”珠子 dummy。
2. prev 指向 dummy。
3. 链接状态: 1 → 2 → 3 → 4 → 5.
2. 找到反转的起点：
1. prev 移动到第一个珠子的位置。
2. prev 指向 1，prev.next 指向 2。
3. 反转珠子：
1. 第一次循环 (i = 0)：
1. temp 指向 3。
2. 2 的 next 指向 4。
3. 3 的 next 指向 2。
4. prev 的 next 指向 3。
2. 第二次循环 (i = 1)：
1. temp 指向 4。
2. 3 的 next 指向 5。
3. 4 的 next 指向 3。
4. prev 的 next 指向 4。

最终的结果就是：1 → 4 → 3 → 2 → 5.

通过这样的步骤，我们可以很容易地把项链上的一部分珠子按照要求反过来了！

最后贴上完整代码：

public ListNode reverseBetween(ListNode head, int m, int n) {
    if (head == null || head.next == null || m == n) {
        return head;
    }

    ListNode dummy = new ListNode(0);
    dummy.next = head;
    ListNode prev = dummy;

    for (int i = 1; i < m; i++) {
        prev = prev.next;
    }

    ListNode current = prev.next;

    for (int i = 0; i < n - m; i++) {
        ListNode temp = current.next;
        current.next = temp.next;
        temp.next = prev.next;
        prev.next = temp;
    }

    return dummy.next;
}