目录
一、前言
反转链表II这道题，可以说是--链表专题--，最经典的一道题，也是在面试中频率最高的一道题目，通常在面试中，面试官可能会从多个方面考察这道题目，所以大家需要对这道题目非常熟悉哦！！
本片博客就来详细的讲讲解一下 反转链表II 的实现方法，让我们的面试变的更加顺利！！！
二、题目描述
给你单链表的头指针
head和两个整数left和right，其中left <= right。请你反转从位置left到位置right的链表节点，返回 反转后的链表 。
三、解题方法
⭐迭代法 --- 带哨兵位（头节点）
🥝 什么是哨兵位头节点？
首先，先来了解一下什么是 哨兵位---头节点 ？
- 它是一个附加的链表结点，该 结点 作为第一个节点，它的数据域不存储任何东西，只是为了操作的方便而引入的。
- 也就是说，如果一个链表有哨兵节点的话，那么链表表的第一个元素应该是链表的第二个节点。
哨兵位 --- 头节点的作用：
- 比如向链表中插入一个节点，对于没有哨兵位的单链表，当待插入的节点为链表的第一个节点，由于没有前驱，需要进行特殊处理，从而代码的复杂性增加。
- 如果有哨兵位头节点，则第一个节点的处理方式与其它节点相同，可以统一进行处理。
🍍 解题思路
- 这道题，其实就是之前讲过的 ---- 反转链表 --- 的升级版
- 如果我们把要 反转的区间 抽取出来，看作一个独立的链表，那么其反转的过程与反转链表的过程是一样的。
- 而现在我们比 反转链表 多了一步是，我们要把抽取出来反转后的区间在拼接回去。
为了把反转后的局部链表拼接回去，我们需要知道四个定位节点：
- reversePre： 反转区间的前一个节点
- reverseHead：反转区间的头节点
- reverseTail： 反转区间的尾节点
- reverseNext： 反转区间的下一个节点
我们要把反转后的链表拼接回去，实际上就是让 reversePre 的 next指针 指向 reverseTail，让reverseHead 的 next指针 指向 reverseNext。
- 题目中的 left 和 right 的数值分别表示第几个节点，我们可以使用一个变量 count 来统计当前节点是第几个节点，初始值为1。
- 当反转区间的头节点为 head 时，head 之前没有节点了，为了统一，我们在头节点之前引入哨兵位头节点 --- pre_head。
- 我们从 哨兵位 头节点开始依次遍历节点，直到
count=left时，刚好到达reversePre。
- 然后从
reversePre的下一个节点开始，即reverseHead，依次反转局部链表，直到count > right。
- 开始反转局部链表，采用三指针迭代法，可以和之前的 反转链表 一样
- 最后将重定向
reversePre的next指针 和reverseHead的next，即将反转后的局部链表重新拼接。
- 最后，返回 哨兵位头节点 的 next 指针
代码：
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right)
{
// 创建一个 哨兵位的 头节点 ，并初始化 值域为 0
// 并将 其的 next 指向 head ---- > pre_head->next = head;
ListNode* pre_head = new ListNode(0 , head);
// 定义反转区间 头节点的上一个节点 ，初始先这只为 哨兵尾--pre
ListNode* reversePre = pre_head;
// 节点编号 --- 开始指向 哨兵位 初始值为 1
int count = 1;
// 找到 反转区间 的头节点 的上一个节点
// 注意 left 是从 head 开始计算的哦！
while(count < left)
{
reversePre = reversePre->next;
count++;
}
// 获取 反转区间的 头节点
ListNode* reverseHead = reversePre->next;
// 反转区间 [left , right]
ListNode* last = nullptr;
ListNode* cur = reverseHead;
ListNode* next;
while(count<=right)
{
next = cur->next;
cur->next = last;
last = cur;
cur = next;
count++;
}
// 重新连接反转后的节点
reversePre->next = last; // 反转区间前一个节点应该连接到反转区间的最后一个节点，即当前的last
reverseHead->next = cur; // 反转区间的头节点应该连接到反转区间的下一个节点，即当前的next
// 返回哨兵尾的 下一位
return pre_head->next;
}
};四、总结与提炼
最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表反转的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握
五、共勉
以下就是我对 反转链表II 的理解，如果有不懂和发现问题的小伙伴，请在评论区说出来哦，同时我还会继续更新对 链表专题 的理解，请持续关注我哦！！！
