反转链表 Ⅱ

92. 反转链表 II.png

断链

设两个游标，移动到 left和 right的位置。然后将这段链表断开来，用 上面的翻转链表方法，翻转完后再接上去，返回即可，代码略。

穿针引线

这个叫法是官方提供的，这里引用官方的图来讲解，比较合适。

官方题解：https://leetcode-cn.com/problems/reverse-linked-list-ii/solution/fan-zhuan-lian-biao-ii-by-leetcode-solut-teyq/

LeetCode官方题解

• cur的下一个节点为 tail

• ①：cur.next = tail.next

• ②：tail.next = pre.next;

• ③：pre.next = tail;

• 以上步骤重复 right - left次，完成。

注：首先三个步骤不能调换顺序，否则丢失链表。第②步，一定是将 tail指向 pre的下一个节点。因为随着 cur往前移动的过程中，翻转到一半的链表的末尾并不是 cur，而是 pre.next，要认准正在翻转中的链表的尾部，只有刚开始翻转的时候，链表尾是 cur，其他时候都不是，属于特殊情况，因此逻辑就按照如上表示。

代码如下：

public class Solution {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode pre = dummyHead;
        for (int i = 0; i < left - 1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        for (int i = 0; i < right - left; i++) {
            ListNode tail = cur.next;   // 每次都要更新这个tail，就在cur的后面
            cur.next = tail.next;
            tail.next = pre.next;
            pre.next = tail;
        }
        return dummyHead.next;
    }

}

• 链表的结构：

class ListNode {
    int val;
    ListNode next;

    ListNode() {
    }

    ListNode(int val) {
        this.val = val;
    }

    ListNode(int val, ListNode next) {
        this.val = val;
        this.next = next;
    }
}