092.反转链表 II

作者：沉默王二
发布时间：2023-10-19T11:51:23.327+0800

---

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

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

示例 2：

输入：head=[5],left=1,right=1

分析

本题依然是链表相关的题目，比较考验我们对节点位置的把握能力。

这次我们打算采用头插法：

利用一个永远指向翻转区域前的节点，然后再利用一个cur变量指向即将要翻转的元素，再加一个next变量指向cur的下一个节点。接着不断移动并修改cur和next，将next替换成next的下一个节点，并且将cur替换为next。

一图胜千言，来看图！

按照图示的方法来进行拆解，大家就能够豁然开朗了。实际上就下面这几个步骤：

• 保持pre的位置不变
• 获取cur的next，赋值给nxt变量
• 修改cur的下一个位置为nxt的next
• 将pre的next修改为nxt。

通过不断变换cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

为了避免代码的冗长，我们加入了dummy这个 头节点的父亲节点，来看题解。

/**

*publicclassListNode{*intval;*ListNodenext;*ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}/classSolution{publicListNodereverseBetween(ListNodehead,intleft,intright){ListNodedummy=newListNode(-1,head);ListNodepre=dummy;for(inti=1;i<=left-1;i++){pre=pre.next;}ListNodecur=pre.next;for(inti=1;i<=right-left;i++){ListNodenext=cur.next;cur.next=next.next;next.next=pre.next;pre.next=next;}returndummy.next;}}

详细分析：

• 为了处理在反转区间内可能会反转到头节点的情况，我们创建了一个虚拟头节点dummy。
• 我们首先找到开始反转的前一个节点pre。这是为了在后续的反转过程中，我们可以轻松地在pre和cur之间插入节点。
• 我们初始化cur为反转区间的第一个节点。
• 在反转过程中，我们每次都取cur的下一个节点next，然后更新cur的next指针，使其跳过next。
• 接着，我们把next插入到pre之后（反转区间的开始）。这样，我们实际上是每次都把cur的下一个节点移动到反转区间的开始位置。
• 反复进行上述操作，直到整个反转区间都被反转完毕。

这个方法的巧妙之处在于，我们不是单纯地在反转区间内交换节点的位置，而是每次都把cur的下一个节点next移动到反转区间的开始位置，这样就达到了反转的效果。

当输入是 head = [1,2,3,4,5], left = 2, right = 4 时，我们来模拟一下整个题解过程。

链表初始状态：

1->2->3->4->5

①. 创建一个虚拟头节点dummy并使其指向head。虚拟头节点的用途是简化操作，尤其是当left为1时，即需要反转包括头节点在内的子段。

dummy(-1)->1->2->3->4->5

②. 初始化pre为虚拟头节点并移动它到反转段的前一个位置。这里left是2，所以pre将移动1次并指向节点1。

pre

dummy(-1)->1->2->3->4->5- cur是反转段的第一个节点，所以它现在指向2。

• 开始反转操作，我们的目标是反转2、3、4这三个节点。

第一次反转（移动节点3到2之前）：

next

dummy(-1)->1->2->3->4->5precur
操作后：dummy(-1)->1->3->2->4->5precurnext

第二次反转（移动节点4到3之前）：

next

dummy(-1)->1->3->2->4->5precurnext
操作后：dummy(-1)->1->4->3->2->5precurnext

③. 所有的反转操作都完成了。新链表现在是：

dummy(-1)->1->4->3->2->5

④. 返回dummy.next ，即新的头节点。结果为：

1->4->3->2->5

所以，对于输入head = [1,2,3,4,5], left = 2, right = 4，经过反转操作后的链表为1 -> 4 -> 3 -> 2 -> 5。

来看一下题解效率。

总结

链表类题目，主要考察的是我们对节点位置的把握能力，以及对链表操作的熟练程度。这道题目的解法非常巧妙，我们可以通过不断地移动cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

力扣链接：https://leetcode.cn/problems/reverse-linked-list-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

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

示例 2：

输入：head=[5],left=1,right=1

分析

本题依然是链表相关的题目，比较考验我们对节点位置的把握能力。

这次我们打算采用头插法：

利用一个永远指向翻转区域前的节点，然后再利用一个cur变量指向即将要翻转的元素，再加一个next变量指向cur的下一个节点。接着不断移动并修改cur和next，将next替换成next的下一个节点，并且将cur替换为next。

一图胜千言，来看图！

按照图示的方法来进行拆解，大家就能够豁然开朗了。实际上就下面这几个步骤：

• 保持pre的位置不变
• 获取cur的next，赋值给nxt变量
• 修改cur的下一个位置为nxt的next
• 将pre的next修改为nxt。

通过不断变换cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

为了避免代码的冗长，我们加入了dummy这个 头节点的父亲节点，来看题解。

/**

*publicclassListNode{*intval;*ListNodenext;*ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}/classSolution{publicListNodereverseBetween(ListNodehead,intleft,intright){ListNodedummy=newListNode(-1,head);ListNodepre=dummy;for(inti=1;i<=left-1;i++){pre=pre.next;}ListNodecur=pre.next;for(inti=1;i<=right-left;i++){ListNodenext=cur.next;cur.next=next.next;next.next=pre.next;pre.next=next;}returndummy.next;}}

详细分析：

• 为了处理在反转区间内可能会反转到头节点的情况，我们创建了一个虚拟头节点dummy。
• 我们首先找到开始反转的前一个节点pre。这是为了在后续的反转过程中，我们可以轻松地在pre和cur之间插入节点。
• 我们初始化cur为反转区间的第一个节点。
• 在反转过程中，我们每次都取cur的下一个节点next，然后更新cur的next指针，使其跳过next。
• 接着，我们把next插入到pre之后（反转区间的开始）。这样，我们实际上是每次都把cur的下一个节点移动到反转区间的开始位置。
• 反复进行上述操作，直到整个反转区间都被反转完毕。

这个方法的巧妙之处在于，我们不是单纯地在反转区间内交换节点的位置，而是每次都把cur的下一个节点next移动到反转区间的开始位置，这样就达到了反转的效果。

当输入是 head = [1,2,3,4,5], left = 2, right = 4 时，我们来模拟一下整个题解过程。

链表初始状态：

1->2->3->4->5

①. 创建一个虚拟头节点dummy并使其指向head。虚拟头节点的用途是简化操作，尤其是当left为1时，即需要反转包括头节点在内的子段。

dummy(-1)->1->2->3->4->5

②. 初始化pre为虚拟头节点并移动它到反转段的前一个位置。这里left是2，所以pre将移动1次并指向节点1。

pre

dummy(-1)->1->2->3->4->5- cur是反转段的第一个节点，所以它现在指向2。

• 开始反转操作，我们的目标是反转2、3、4这三个节点。

第一次反转（移动节点3到2之前）：

next

dummy(-1)->1->2->3->4->5precur
操作后：dummy(-1)->1->3->2->4->5precurnext

第二次反转（移动节点4到3之前）：

next

dummy(-1)->1->3->2->4->5precurnext
操作后：dummy(-1)->1->4->3->2->5precurnext

③. 所有的反转操作都完成了。新链表现在是：

dummy(-1)->1->4->3->2->5

④. 返回dummy.next ，即新的头节点。结果为：

1->4->3->2->5

所以，对于输入head = [1,2,3,4,5], left = 2, right = 4，经过反转操作后的链表为1 -> 4 -> 3 -> 2 -> 5。

来看一下题解效率。

总结

链表类题目，主要考察的是我们对节点位置的把握能力，以及对链表操作的熟练程度。这道题目的解法非常巧妙，我们可以通过不断地移动cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

力扣链接：https://leetcode.cn/problems/reverse-linked-list-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

本题解同时收录在星球专栏《二哥的 LeetCode 刷题笔记》中，专栏托管在语雀平台上（更方便你沉浸式阅读和做笔记），访问地址和密码：https://t.zsxq.com/6iuzn6I

题意

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

难度

中等

示例

示例 1：

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

示例 2：

输入：head=[5],left=1,right=1

分析

本题依然是链表相关的题目，比较考验我们对节点位置的把握能力。

这次我们打算采用头插法：

利用一个永远指向翻转区域前的节点，然后再利用一个cur变量指向即将要翻转的元素，再加一个next变量指向cur的下一个节点。接着不断移动并修改cur和next，将next替换成next的下一个节点，并且将cur替换为next。

一图胜千言，来看图！

按照图示的方法来进行拆解，大家就能够豁然开朗了。实际上就下面这几个步骤：

• 保持pre的位置不变
• 获取cur的next，赋值给nxt变量
• 修改cur的下一个位置为nxt的next
• 将pre的next修改为nxt。

通过不断变换cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

为了避免代码的冗长，我们加入了dummy这个 头节点的父亲节点，来看题解。

/**

*publicclassListNode{*intval;*ListNodenext;*ListNode(){}ListNode(intval){this.val=val;}ListNode(intval,ListNodenext){this.val=val;this.next=next;}}/classSolution{publicListNodereverseBetween(ListNodehead,intleft,intright){ListNodedummy=newListNode(-1,head);ListNodepre=dummy;for(inti=1;i<=left-1;i++){pre=pre.next;}ListNodecur=pre.next;for(inti=1;i<=right-left;i++){ListNodenext=cur.next;cur.next=next.next;next.next=pre.next;pre.next=next;}returndummy.next;}}

详细分析：

• 为了处理在反转区间内可能会反转到头节点的情况，我们创建了一个虚拟头节点dummy。
• 我们首先找到开始反转的前一个节点pre。这是为了在后续的反转过程中，我们可以轻松地在pre和cur之间插入节点。
• 我们初始化cur为反转区间的第一个节点。
• 在反转过程中，我们每次都取cur的下一个节点next，然后更新cur的next指针，使其跳过next。
• 接着，我们把next插入到pre之后（反转区间的开始）。这样，我们实际上是每次都把cur的下一个节点移动到反转区间的开始位置。
• 反复进行上述操作，直到整个反转区间都被反转完毕。

这个方法的巧妙之处在于，我们不是单纯地在反转区间内交换节点的位置，而是每次都把cur的下一个节点next移动到反转区间的开始位置，这样就达到了反转的效果。

当输入是 head = [1,2,3,4,5], left = 2, right = 4 时，我们来模拟一下整个题解过程。

链表初始状态：

1->2->3->4->5

①. 创建一个虚拟头节点dummy并使其指向head。虚拟头节点的用途是简化操作，尤其是当left为1时，即需要反转包括头节点在内的子段。

dummy(-1)->1->2->3->4->5

②. 初始化pre为虚拟头节点并移动它到反转段的前一个位置。这里left是2，所以pre将移动1次并指向节点1。

pre

dummy(-1)->1->2->3->4->5- cur是反转段的第一个节点，所以它现在指向2。

• 开始反转操作，我们的目标是反转2、3、4这三个节点。

第一次反转（移动节点3到2之前）：

next

dummy(-1)->1->2->3->4->5precur
操作后：dummy(-1)->1->3->2->4->5precurnext

第二次反转（移动节点4到3之前）：

next

dummy(-1)->1->3->2->4->5precurnext
操作后：dummy(-1)->1->4->3->2->5precurnext

③. 所有的反转操作都完成了。新链表现在是：

dummy(-1)->1->4->3->2->5

④. 返回dummy.next ，即新的头节点。结果为：

1->4->3->2->5

所以，对于输入head = [1,2,3,4,5], left = 2, right = 4，经过反转操作后的链表为1 -> 4 -> 3 -> 2 -> 5。

来看一下题解效率。

总结

链表类题目，主要考察的是我们对节点位置的把握能力，以及对链表操作的熟练程度。这道题目的解法非常巧妙，我们可以通过不断地移动cur和nxt的相对位置，将nxt提到pre后面，与此同时cur的位置也就自然而然地向后移动了。

力扣链接：https://leetcode.cn/problems/reverse-linked-list-ii/

一步一个脚印

不积跬步无以至千里，不积小流无以成江海。LeetCode - 100天从算法小白到卷王正式启动了，我们计划周一到周五至少每天更新一篇，周六周日更新一篇，目标 300 道 LeetCode 经典题。

PDF 版本目前只针对**二哥编程星球 的球友开放，如果你也想一起打卡学习算法的话，戳链接 **加入我们吧。

一个人可以走得很快，但一群人才能走得更远。二哥编程星球 （目前已有 3700 多名球友加入）里面的每个球友都非常的友善，除了鼓励你，还会给你提出合理的建议，一起冲！

            知识星球
            
    
    
        
        扫码加入星球
        查看更多优质内容
    
    https://wx.zsxq.com/mweb/views/joingroup/join_group.html?group_id=15522885221412