---

前言

提示：人啊，果然跟花一样，开花前的等待无比漫长，绽放的魅力却转瞬即逝。

---

链表反转|指定区间内

参考题目：92. 反转链表 II - 力扣（LeetCode）

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

当然我们上次已经教大家怎么将一个链表翻转过来了👌，今天我们就来看看他的变题（当然难度会更高👍

依旧还是两种解法：

我们姑且😒叫他头插法和穿针引线法（主要还是不会起名字🤣：

头插法：

我们先来画个图来看下效果：

中间状态变化：

当然：

如果left和right的范围很大的，正好是头节点和尾节点的话，找到left和right需要遍历一次，

反转他们的话还需要一次遍历，这样的话复杂度为O(N),但是需要遍历两次，想一下有没有遍历一次的方法有的，当然可以这样做；

整体步骤：

1. 创建一个虚拟节点（dummyNode),per = dummyNode;
2. 循环left - 1 次 让pre停留在letf的前一个节点上
3. 常见cur节点（首位反转），next节点
4. 开始反转

/*** 方法1：头插法** @param head* @param left* @param right* @return*/public static ListNode reverseBetween2(ListNode head, int left, int right) {// 设置虚拟头节点ListNode dummyNode = new ListNode(-1);dummyNode.next = head;// 用一在保留引用ListNode pre = dummyNode;for(int i = 0; i < left - 1; i++){pre = pre.next;} // 找到left的前一个节点ListNode cur = pre.next;ListNode next = null;for(int i = 0; i < right - left; i++){next = cur.next;cur.next = next.next;next.next = pre.next; // 这一点不太理解pre.next = next;}return dummyNode.next;}

穿针引线法：

这种方法思路很简单，但是书写起来很难，需要你对链表有一定的熟悉程度，话不多说，我们开始尝试一下吧🥰。

首先看下图：

这里写一下思路：

1. 先将待反转的区域反转好
2. 改变指针域（即 pre.next = right; left.next = succ)
   
   
   注意：链表反转值得是指针域的方向（一定要注意）

建议复习一下（不带头节点的链表反转）记住一下图：

/*** 基本的反转方法** @param head* @return*/public static ListNode  reverseList(ListNode head) {ListNode pre = null;ListNode cur = head;while(cur != null) {ListNode next = cur.next;cur.next = pre;pre = cur;cur = next;}return pre;}

/*** 方法2：穿针引线法** @param head* @param left* @param right* @return*/public static ListNode reverseBetween(ListNode head, int left, int right) {// 因为头节点频繁变化，使用虚拟节点可以避免这样的问题ListNode dummyNode = new ListNode(-1);dummyNode.next = head;ListNode pre = dummyNode;// 第一步找到left 和 righe 节点// 让per 做到left的前一个节点for(int i = 0; i < left - 1; i++){pre = pre.next;}ListNode rightNode = pre;// 第二步 pre 继续前进 right - left + 1 来到right节点for(int i = 0; i < right - left + 1; i++){rightNode = rightNode.next;}// 第三步 切出子链表ListNode leftNode = pre.next;ListNode cucc = rightNode.next;// 切断连接pre.next = null;rightNode.next = null;// 第四步 反转链表reverseList(leftNode);// 第五步 更改指针域（接回原来的链表）pre.next = rightNode;leftNode.next = cucc;return dummyNode.next;}

---

总结

这里需要重点理解一下反转链表，注意指针域的变化