将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 &preview=true)
，空间复杂度 &preview=true)
。
例如：
给出的链表为
, 
,
返回
.
例如：
给出的链表为
返回
数据范围： 链表长度 
，
，链表中每个节点的值满足 
要求：时间复杂度 )
，空间复杂度
进阶：时间复杂度 ，空间复杂度 )
[编程题]链表内指定区间反转
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public 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
if (head == null || head.next == null || m == n) {
return head;
}
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode pre = dummy;
ListNode cur = head;
ListNode nxt = null;
for (int i = 0; i < m - 1; i++) {
pre = pre.next;
}
cur = pre.next;
if (cur == null || cur.next == null) {
return head;
}
ListNode grouppre = null;
ListNode grouphead = cur;
for (int i = m; i <= n; i++) {
nxt = cur.next;
cur.next = grouppre;
grouppre = cur;
cur = nxt;
}
grouphead.next = cur;
pre.next = grouppre;
return dummy.next;
}
}
发表于 2025-11-13 23:22:38
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
// 若为空或长度为1直接返回
if(head == null || head.next == null) return head;
// 两种情况
// 1 第一个节点不用反转，结果返回时返回原链表头结点
// 2 第一个节点在反转区间，结果返回反转后的最后一个节点
ListNode res = head;
ListNode pre = null;
// 跳过不需要反转的节点
for(int i = 0;i < m-1;i++) {
pre = head;
head = head.next;
}
// 保存当前head所在位置为后续连接末尾的节点做准备
ListNode tail = head;
// 保存head前一个节点为第一种情况的连接做准备
// 第二种情况下preHead = pre 为空
ListNode preHead = pre;
pre = head;
// 引入下一个节点 开始反转
ListNode nex = head.next;
for(int i = 0;i < n-m;i++) {
head = nex;
nex = head.next;
head.next = pre;
pre = head;
}
// 分情况返回
if(preHead != null) {
preHead.next.next = nex;
preHead.next = head;
return res;
} else {
tail.next = nex;
return head;
}
}
发表于 2025-10-17 16:19:13
回复(0)
public class Solution {
public ListNode reverseBetween (ListNode head, int m, int n) {
//加个表头
ListNode res = new ListNode(-1);
res.next = head;
//前序节点
ListNode pre = res;
//当前节点
ListNode cur = head;
//找到m
for(int i = 1; i < m; i++){
pre = cur;
cur = cur.next;
}
//从m反转到n
// 这段代码看似复杂，但本质上是把cur后面的元素[插入]到pre后面
// 只是改变了cur,temp和pre的后继结点（变动了3个箭头）；cur和pre不变
for(int i = m; i < n; i++){
ListNode temp = cur.next;
cur.next = temp.next;
temp.next = pre.next;
pre.next = temp;
}
//返回去掉表头
// 这里不能返回head，因为当m=1时，head不再是第一个结点
return res.next;
}
}
发表于 2025-08-03 13:08:42
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
Stack<Integer> stack = new Stack<>();
ListNode cur = head;
ListNode curN = head;
//找到需要反转的第一个元素
for (int i = 0; i < m - 1; i++) {
cur = cur.next;
}
ListNode prev = cur;
//先放元素进栈
for (int i = 0; i < n - m + 1; i++) {
stack.add(cur.val);
cur = cur.next;
}
//出栈
for (int i = 0; i < n - m + 1; i++) {
int tmp = stack.pop();
prev.val = tmp;
prev = prev.next;
}
return curN;
}
}
发表于 2025-06-16 23:10:52
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public 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
//如果链表为空，直接返回空
if (head == null) {
return null;
}
//如果 m == n，说明不需要反转，直接返回原链表
else if (m == n) {
return head;
}
//创建一个虚拟头节点 pre，用于处理从头开始反转的情况（比如 m=1）
//p1 是 pre 的指针，用来遍历找到第 m - 1 个节点的位置
else {
ListNode pre = new ListNode(0), p1 = pre;
pre.next = head;
//将 p1 指到第 m - 1 个节点，此时：
//p1.next 就是需要开始反转的第一个节点（即第 m 个节点）
for (int i = 1; i < m; i++) {
p1 = p1.next;
}
//p2 指向当前要反转的起始节点（即第 m 个节点）
//temp 记录操作前的节点数据，后续用于连接后半段链表
ListNode p2 = p1.next, temp = p1.next;
//使用“头插法”,把 p2 所在的节点依次插入到 p1 后面，从而实现局部反转
for (int j = m; j <= n; j++) {
//node = p2.next: 保存下一个要反转的节点
ListNode node = p2.next;
//p2.next = p1.next: 当前节点插入到 p1 后面
p2.next = p1.next;
//p1.next = p2: 插入完成
p1.next = p2;
//p2 = node: 继续处理下一个节点
p2 = node;
}
//将原来的第一个反转节点（temp）指向 p2，也就是反转后的剩余部分
temp.next = p2;
//返回 pre.next，确保即使头节点被反转了也能正确返回新头节点
return pre.next;
}
}
}
发表于 2025-05-12 18:43:58
回复(0)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
ListNode[] nodes = new ListNode[n+1];
List<ListNode> list = new ArrayList<>();
int loc=1;
while(head != null) {
if(loc<m) {
nodes[loc] = head;
} else if(loc>=m && loc<=n) {
nodes[n-(loc-m)] = head;
} else {
list.add(head);
}
head = head.next;
loc++;
}
head = new ListNode(-1);
ListNode r = head;
for(int i=1; i<=n; i++) {
System.out.println(nodes[i].val);
r.next = nodes[i];
r = r.next;
}
for(int i=0; i<list.size(); i++) {
System.out.println(list.get(i).val);
r.next = list.get(i);
r = r.next;
}
r.next = null;
return head.next;
}
}
发表于 2025-04-12 04:00:38
回复(0)
public class Solution {
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
if (m == n) {
return head;
}
ListNode temp = head;
List<ListNode> cache = new ArrayList<>(n-m+1);
int sign = 1;
while(head!=null){
if(sign>=m&&sign<=n){
cache.add(head);
}
head= head.next;
sign++;
}
int left = 0;
int right = cache.size()-1;
while(left<right){
ListNode leftNode = cache.get(left);
ListNode rightNode = cache.get(right);
int leftTemp = leftNode.val;
leftNode.val = rightNode.val;
rightNode.val = leftTemp;
left++;
right--;
}
return temp;
}
}
发表于 2025-01-09 22:31:09
回复(0)
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param head ListNode类
* @param m int整型
* @param n int整型
* @return ListNode类
*/
public ListNode reverseBetween (ListNode head, int m, int n) {
if(m==n) return head;
ListNode const_head = head;
ListNode s = null;
for(int i=0;i<m-1;i++){
s = head;
head = s.next;
}
ListNode prev = null;
ListNode last = head;
for(int i=m-2;i<n-1;i++){
ListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
if(s != null) s.next = prev; else const_head = prev;
last.next = head;
return const_head;
}
}
发表于 2024-08-15 18:13:09
回复(0)
利用栈
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
Stack stack = new Stack();
ListNode temp = new ListNode(0);
ListNode temp1 = temp;
int count = 1;
while (head != null) {
if (count >= m && count <= n) {
stack.push(head);
} else {
if (stack.isEmpty()) {
temp.next = head;
temp = head;
} else {
while (!stack.isEmpty()) {
ListNode pop = stack.pop();
temp.next = pop;
temp = pop;
}
temp.next = head;
temp = head;
}
}
count++;
head = head.next;
}
if (!stack.isEmpty()) {
while (!stack.isEmpty()) {
ListNode pop = stack.pop();
temp.next = pop;
temp = pop;
}
temp.next = null;
}
return temp1.next;
}
发表于 2024-08-06 09:59:56
回复(1)
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public 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.先定义两个指针start和end，分别指向前方的m位置和后方的n位置
ListNode start = null;
ListNode end = null;
// 2.记录start指针的上一个结点allPre，end指针的下一个结点allPost
ListNode allPre = head; // 先把allPre指向head这个整个链表的起点，随着查找m可以往后移动head
ListNode allPost = null;
// 准备找到m和n位置对应的start和end，以及对应的allPre和allPost
ListNode cur = head;
for (int i = 1; cur != null; cur = cur.next, i++) {
if (i == m) {
start = cur;
}
if (i == n) {
end = cur;
allPost = end.next;
break;
}
// 只有在i>1（让allPre落后一位）且i<m（还没找到start）时更新allPre
if (i > 1 && i < m) {
allPre = allPre.next;
}
}
System.out.println("allPre: " + (allPre != null ? allPre.val : "null"));
System.out.println("start: " + (start != null ? start.val : "null"));
System.out.println("end: " + (end != null ? end.val : "null"));
System.out.println("allPost: " + (allPost != null ? allPost.val : "null"));
// 3.执行类似于上一题的方法，反转start和end之间的链表，返回反转后的起点newStart和终点newEnd
ListNode newStart = end;
ListNode newEnd = start;
// 只有strat和end不指向同一个结点（反转区间>1）时，才有反转的必要
if (start != end) {
ListNode newPre = start;
ListNode newCur = start.next;
ListNode newNext = newCur.next;
// 此处不用管newPre的next指向何方，因为这个newPre就是newEnd，是数组反转后的结尾，下文会令其指向allPost
while(newCur != allPost) {
newNext = newCur.next;
newCur.next = newPre;
System.out.println("结点" + newCur.val + "的反转已完成");
newPre = newCur;
newCur = newNext;
}
}
// 4.令allPre指向newStart，令allPost指向newEnd
// 注意allPre的边界判断！allPre可能与newEnd（start）重合！
if (allPre == newEnd) {
// 如果allPre 跟 newEnd（start） 是同一个结点（m=1的情况），说明start前面没有任何元素，这时可以直接移动head到链表区间反转后的起点，令head = newStart
allPre = newStart;
head = allPre;
} else {
// 否则，是正常情况，令allPre指向newStart，从newStart到newEnd是反转区间
allPre.next = newStart;
}
newEnd.next = allPost;
System.out.println("newEnd结点" + newEnd.val + "的下一个结点allPost是" + (allPost != null ? allPost.val : "null"));
System.out.println("allPre结点" + allPre.val + "的下一个结点newStart是" + (newStart != null ? newStart.val : "null"));
System.out.println("head结点" + head.val);
return head;
}
}
发表于 2024-07-26 23:21:15
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
//将链条分为head…………xNode mNode ………… nNode（这个是nNode节点的下一个）…………
ListNode node = head;
ListNode mNode = null;
ListNode nNode = null;
ListNode xNode = null;
int index = 1;
if (node.next == null || m == n)
return node;
while (node != null) {
if (m == 1) {
mNode = head;
break;
}
if (index == m - 1) {
mNode = node.next;
node.next = null;
xNode = node;
}
node = node.next;
index++;
}
node = mNode;
while (node != null) {
if (index == n) {
nNode = node.next;
node.next = null;
}
node = node.next;
index++;
}
ListNode prev = nNode;
ListNode curr = mNode;
while (curr != null) {
ListNode nextTemp = curr.next; // 保存当前节点的下一个节点
curr.next = prev; // 反转当前节点的next指针
prev = curr; // 移动prev到当前节点
curr = nextTemp; // 移动curr到下一个节点
//如果第一项就开始反转，那么xNode就为null，得重新找到反转链表的最后一个节点，其实这个节点就是头节点
}
if (xNode != null) {
xNode.next = prev;
return head;
} else {
return prev;
}
}
}
//将链条分为head…………xNode mNode ………… nNode（这个是nNode节点的下一个）…………
ListNode node = head;
ListNode mNode = null;
ListNode nNode = null;
ListNode xNode = null;
int index = 1;
if (node.next == null || m == n)
return node;
while (node != null) {
if (m == 1) {
mNode = head;
break;
}
if (index == m - 1) {
mNode = node.next;
node.next = null;
xNode = node;
}
node = node.next;
index++;
}
node = mNode;
while (node != null) {
if (index == n) {
nNode = node.next;
node.next = null;
}
node = node.next;
index++;
}
ListNode prev = nNode;
ListNode curr = mNode;
while (curr != null) {
ListNode nextTemp = curr.next; // 保存当前节点的下一个节点
curr.next = prev; // 反转当前节点的next指针
prev = curr; // 移动prev到当前节点
curr = nextTemp; // 移动curr到下一个节点
//如果第一项就开始反转，那么xNode就为null，得重新找到反转链表的最后一个节点，其实这个节点就是头节点
}
if (xNode != null) {
xNode.next = prev;
return head;
} else {
return prev;
}
}
}
发表于 2024-07-16 08:48:48
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
ListNode pre=new ListNode(0) ,p1=pre;
pre.next=head;
for(int i=1;i<m;i++){
p1=p1.next;
}
ListNode p2=p1.next ,temp=p1.next;
for(int i=m;i<=n;i++){
ListNode node=p2.next;
p2.next=p1.next;
p1.next=p2;
p2=node;
}
temp.next=p2;
return pre.next;
}
发表于 2024-06-02 13:43:15
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
if (head == null || m >= n) {
return head;
}
ListNode rootNode = new ListNode(0);
rootNode.next = head;
ListNode pre = null;
ListNode mNode = null;
ListNode nNode = null;
ListNode mmNode = null;
int k = 1;
int j = 0;
while(k <= n && head!= null){
if (k+1 == m){
mNode = head;
mmNode = head.next;
j++;
}else if(k == m && j == 0){
mNode = rootNode;
mmNode = head;
}
if (k == n){
nNode = head.next;
}
if (k >= m && k <= n){
ListNode temp = head.next;
head.next = pre;
pre = head;
head = temp;
}else{
head = head.next;
}
k++;
}
mNode.next = pre;
mmNode.next = nNode;
return rootNode.next; // 返回链表的头节点
} 为解题而解题硬凑的，算法还是Java排第一的那个妙
发表于 2024-05-28 10:19:36
回复(0)
自己的想法，有些麻烦
import java.util.*;
/*
* public class ListNode {
* int val;
* ListNode next = null;
* public ListNode(int val) {
* this.val = val;
* }
* }
*/
public 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
ListNode tmp = head;
ListNode pre, cur, preNode = null, tailNode = null;
int i = 0;
//范围包含头结点，则创建一个结点使得 next 域指向 head
if (m == 1) {
preNode = new ListNode(0);
preNode.next = head;
}
//遍历链表找到起始节点
while (tmp != null) {
//若范围不包含头节点，则记录范围两头相邻的节点preNode、tailNode
if (i == m - 2) {
preNode = tmp;
}
if (i == n) {
tailNode = tmp;
}
tmp = tmp.next;
i++;
}
pre = null;
cur = preNode.next;
//反转链表
while (cur != null) {
if (cur == preNode.next) {
pre = tailNode;
}
tmp = cur.next;
cur.next = pre;
pre = cur;
cur = tmp;
if (cur == tailNode) {
preNode.next = pre;
break;
}
}
if (m == 1) {
return preNode.next;
}
return head;
}
}
发表于 2024-05-15 17:36:39
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
