No.92 反转链表② (Medium)

题目描述

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

示例：

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

思路

头插法

1. 找到要翻转的结点的前一个结点，标记为guard结点（示例中为1）；
2. 要翻转的第一个结点，标记为Point结点（示例中的2）；
3. 开始循环；
4. 循环第一次；
5. 用removed保存point后边那个结点（即要移除的结点，示例中的3）;
6. point总是指向point后的第二个结点，即2 -> 4；(point.next = point.next.next;)
7. 总是将removed结点插入到guard结点之后，即将3插入到1之后，形成1->3->2->4->5; removed.next = guard.next; guard.next = removed;
8. 循环第二次，仍然还是将新的removed结点插入到guard结点以后
9. 新的removed结点仍然是point之后的结点，即2后边的4；
10. point指向point后的第二个结点，即2 -> 5;
11. 将removed插入到guard结点之后，即1->4->3->2->5;

代码

class Solution {
    public ListNode reverseBetween(ListNode head, int left, int right) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode guard = dummy;
        ListNode point = head;
        // 例如，left = 2; right = 4;
        // guard -> 1; point -> 2;
        for (int step = 0; step < left - 1; step++) {
            guard = guard.next;
            point = point.next;
        }
        // 头插次数为right - left次
        // 将3插入，将4插入，共两次，即i = 0时进行一次，i = 1时进行一次，因此是i < right - left;
        for (int i = 0; i < right - left; i++) {
            ListNode removed = point.next;
            point.next = point.next.next;
            removed.next = guard.next;
            guard.next = removed;
        }
        return dummy.next;
    }
}

总结

头插时：

1. 首先用removed保存要移动的结点： ListNode removed = point.next;
2. 在1中用了临时变量来保存point.next, 接下来就改变point.next的指向： point.next = point.next.next;
3. 将removed插入到guard之后，需要首先让removed.next指向guard.next;
4. 然后让guard.next = removed;

注意，3和4不能交换顺序，因为如果交换了，4先执行，那么guard后面的结点变成了removed，原先的guard后边的结点就会被丢失，就无法让removed结点指向guard后边的结点了。