【算法专题--链表】反转链表II--高频面试题（图文详解，小白一看就会！！！）

【算法专题--链表】反转链表II--高频面试题（图文详解，小白一看就会！！！）

引用

CSDN

1.

https://blog.csdn.net/weixin_45031801/article/details/139694781

目录
一、前言
二、题目描述
三、解题方法
⭐迭代法 --- 带哨兵位（头节点）
🥝 什么是哨兵位头节点？
🍍 解题思路
四、总结与提炼

一、前言

反转链表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;
    }
};  

四、总结与提炼

最后我们来总结一下本文所介绍的内容，本文讲解来一道力扣中有关链表反转的题目，这道题目是校招笔试面试中有关链表章节非常高频的一道题目，大家下去一定要自己再画画图，分析一下，把这段代码逻辑自己实现一遍，才能更好地掌握