可视化图解算法：链表指定区间反转
原创
可视化图解算法：链表指定区间反转
原创
用户11589437
修改于 2025-07-11 11:04:38
修改于 2025-07-11 11:04:38
代码可运行
运行总次数：0
代码可运行
1. 题目
描述
给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
示例1
输入：输入：head = [1,2,3,4,5], left = 2, right = 4 输出：[1,4,3,2,5]
示例 2
输入：head = [5], left = 1, right = 1 输出：[5]
提示：
- 链表中节点数目为
n 1 <= n <= 500-500 <= Node.val <= 5001 <= left <= right <= n
2. 解题思路
第1步：定义一个临时链表头节点。
第2步：定义（找到）截取区间外的指针变量：pre、post，截取区间指针变量：left、right。
第3步：切断原连接。
第4步：翻转局部链表。
链表的局部反转，可以参考上一篇讲解的《可视化图解算法：反转链表》。
第5步：接回原来的链表。
3. 编码实现
3.1 Python编码实现
class ListNode:
def __init__(self, x):
self.val = x # 链表的数值域
self.next = None # 链表的指针域
# 从链表节点尾部添加节点
def insert_node(node, value):
if node is None:
print("node is None")
return
# 创建一个新节点
new_node = ListNode(value)
cur = node
# 找到链表的末尾节点
while cur.next is not None:
cur = cur.next
# 末尾节点的next指针域连接新节点
cur.next = new_node
# 打印链表（从链表头结点开始打印链表的值）
def print_node(node):
cur = node
# 遍历每一个节点
while cur is not None:
print(cur.val, end="\t")
cur = cur.next # 更改指针变量的指向
print()
def reverseList(left):
if left is None:
return
pre = None # （操作的）前序节点
cur = left # （操作的）当前节点
nxt = left # （操作的）下一个节点
while cur is not None:
nxt = cur.next
cur.next = pre
pre = cur
cur = nxt
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param head ListNode类
# @param m int整型
# @param n int整型
# @return ListNode类
#
class Solution:
def reverseBetween(self, head: ListNode, m: int, n: int) -> ListNode:
# write code here
# 1. 定义一个临时链表头节点
tmp_head = ListNode(-1)
tmp_head.next = head
# 2.定义（找到）截取区间外的指针变量：pre、post，截取区间指针变量：left、right
pre = tmp_head
for i in range(m - 1):
pre = pre.next
left = pre.next
right = tmp_head
for i in range(n):
right = right.next
post = right.next
# 3.切断链接
pre.next = None
right.next = None
# 4. 翻转局部链表
reverseList(left)
# 5.接回原来的链表
pre.next = right
left.next = post
return tmp_head.next
if __name__ == '__main__':
root = ListNode(1)
insert_node(root, 2)
insert_node(root, 3)
insert_node(root, 4)
insert_node(root, 5)
print_node(root)
s = Solution()
head = s.reverseBetween(root, 2, 4)
print_node(head)
3.2 Java编码实现
package LL02;
import javax.swing.plaf.nimbus.NimbusLookAndFeel;
public class Main {
//定义链表节点
static class ListNode {
private int val; //链表的数值域
private ListNode next; //链表的指针域
public ListNode(int data) {
this.val = data;
this.next = null;
}
}
//添加链表节点
private static void insertNode(ListNode node, int data) {
if (node == null) {
return;
}
//创建一个新节点
ListNode newNode = new ListNode(data);
ListNode cur = node;
//找到链表的末尾节点
while (cur.next != null) {
cur = cur.next;
}
//末尾节点的next指针域连接新节点
cur.next = newNode;
}
//打印链表（从头节点开始打印链表的每一个节点）
private static void printNode(ListNode node) {
ListNode cur = node;
//遍历每一个节点
while (cur != null) {
System.out.print(cur.val + "\t");
cur = cur.next; //更改指针变量的指向
}
System.out.println();
}
public static class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween(ListNode head, int m, int n) {
// write code here
//1. 定义一个临时链表头节点
ListNode tmpHead = new ListNode(-1);
tmpHead.next = head;
//2.定义（找到）截取区间外的指针变量：pre、post，截取区间指针变量：left、right
ListNode pre = tmpHead;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
ListNode left = pre.next;
ListNode right = tmpHead;
for (int i = 0; i < n; i++) {
right = right.next;
}
ListNode post = right.next;
//3.切断链接
pre.next = null;
right.next = null;
//4.反转局部链表
reverseList(left);
//5.接回原来的链表
pre.next = right;
left.next = post;
return tmpHead.next;
}
private void reverseList(ListNode left) {
ListNode pre = null; //前序节点
ListNode cur = left; //（操作的）当前节点
ListNode nxt = left;//（操作的）下一个节点
while (cur != null) {
nxt = cur.next;
cur.next = pre;
pre = cur;
cur = nxt;
}
}
}
public static void main(String[] args) {
ListNode root = new ListNode(1);
insertNode(root, 2);
insertNode(root, 3);
insertNode(root, 4);
insertNode(root, 5);
printNode(root);
Solution solution = new Solution();
ListNode head = solution.reverseBetween(root, 2, 4);
printNode(head);
}
}
3.3 Golang编码实现
package main
import (
"fmt"
)
type ListNode struct {
Val int //链表的数值域
Next *ListNode //链表的指针域
}
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
func reverseBetween(head *ListNode, m int, n int) *ListNode {
// write code here
//1. 定义一个临时链表头节点
tempHead := &ListNode{Val: -1}
tempHead.Next = head
//2.定义（找到）截取区间外的指针变量：pre、post，截取区间指针变量：left、right
pre := tempHead
for i := 0; i < m-1; i++ {
pre = pre.Next
}
left := pre.Next
right := tempHead
for i := 0; i < n; i++ {
right = right.Next
}
post := right.Next
//3.切断链接
pre.Next = nil
right.Next = nil
//4.翻转局部链表
reverseList(left)
//5.接回原来的链表
pre.Next = right
left.Next = post
return tempHead.Next
}
func reverseList(left *ListNode) {
var pre *ListNode //（操作的）前序节点
cur := left //（操作的）当前节点
nxt := left //（操作的）下一个节点
for cur != nil {
nxt = cur.Next
cur.Next = pre
pre = cur
cur = nxt
}
}
func main() {
root := &ListNode{Val: 1}
root.Insert(2)
root.Insert(3)
root.Insert(4)
root.Insert(5)
root.Print()
node := reverseBetween(root, 2, 4)
node.Print()
}
// Insert 从链表节点尾部添加节点
func (ln *ListNode) Insert(val int) {
if ln == nil {
return
}
//创建一个新节点
newNode := &ListNode{Val: val}
cur := ln
//找到链表的末尾节点
for cur.Next != nil {
cur = cur.Next
}
//末尾节点的next指针域连接新节点
cur.Next = newNode
}
// Print 从链表头结点开始打印链表的值
func (ln *ListNode) Print() {
if ln == nil {
return
}
cur := ln
//遍历每一个节点
for cur != nil {
fmt.Print(cur.Val, "\t")
cur = cur.Next //更改指针变量的指向
}
fmt.Println()
}
4.小结
对于链表内指定区间反转的反转，可以通过5步操作完成：
（1）定义一个临时链表头节点；（2）定义（找到）截取区间外的指针变量：pre、post，截取区间指针变量：left、right；（3）切断链接；（4）翻转局部链表；（5）接回原来的链表。对于第4步局部反转用到了上一篇所讲的内容。
对于链表的相关操作，我们总结了一套【可视化+图解】方法，依据此方法来解决链表相关问题，链表操作变得易于理解，写出来的代码可读性高也不容易出错。具体也可以参考视频详细讲解。
视频讲解：B站 @好易学数据结构
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读
目录
腾讯云开发者
