将一个节点数为 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) {
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)
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
if (m == n) {
return head;
}
int index = 1;
ListNode start = new ListNode(0);
start.next = head;
ListNode mIndex = head;
while (index < m) {
index++;
start = mIndex;
mIndex = mIndex.next;
}
ListNode startNext = start.next;
while (mIndex.next != null & index < n) {
start.next = mIndex.next;
mIndex.next = start.next.next;
start.next.next = startNext;
startNext = start.next;
index++;
}
return m == 1 ? startNext : head;
}
发表于 2024-05-09 14:35:44
回复(0)
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 root = new ListNode(-1); root.next = head; ListNode left = null; ListNode right = null; ListNode begin = root; ListNode end = root; for(int i=0;i<m;i++){ left = begin; begin = begin.next; } for(int i=0;i<n;i++){ end = end.next; right = end.next; } left.next = null; end.next = null; reverseNode(begin); left.next = end; begin.next = right; return root.next;}
public ListNode reverseNode (ListNode head){
if(head == null) { return null; } ListNode pre = null; ListNode next = null; while(head != null) { next = head.next; head.next = pre; pre = head; head = next; } return pre;}
}
编辑于 2024-03-17 16:35:26
回复(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) {
ListNode pre=new ListNode(-1);
pre.next=head;
ListNode cp=head;
ListNode cur=head;
ListNode start=pre;
int left=1;
while(left<m){start=cp;cp=cp.next;cur=cur.next;left++;}
while(left<n){cur=cur.next;left++;}
ListNode last=cur.next;
int s=m;
while(s<=n){
ListNode next=cp.next;
cp.next=last;
last=cp;
cp=next;
s++;
}
start.next=cur;
return pre.next;
// write code here
}
}
编辑于 2024-03-09 11:51:43
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
//此情况无需反转
if(m == n ) {
return head;
}
//虚拟节点，防止从第一个节点就开始反转（m=1的情况）
ListNode res = new ListNode(-1);
res.next = head;
//指针，指向反转节点的 前一个节点，用于连接 反转后的节点
ListNode perfix = res;
ListNode p = head;
//找到第一个反转的开始节点
while(p.next != null && m > 1) {
p = p.next;
perfix = perfix.next;
m--;
n--;
}
ListNode reversNode = null;
//开始反转
while(p != null && n > 0) {
ListNode tmp = p.next;
p.next = reversNode;
reversNode = p;
p = tmp;
n--;
}
//reversNode 就是反转后的节点
perfix.next = reversNode;
ListNode s = reversNode;
//指针s，找到反转后的链表 的最后一个节点
while (s.next != null) {
s = s.next;
}
//将这个节点连接上p
s.next = p;
return res.next;
}
发表于 2024-03-08 23:42:58
回复(0)
public ListNode reverseBetween (ListNode head, int m, int n) {
// write code here
if(head == null || head.next == null){
return head;
}
List<Integer> list = new ArrayList<>();
while(head != null){
list.add(head.val);
head = head.next;
}
if(list.size() == 1){
return head;
}
List<Integer> list2 = list.subList(m-1,n);
Collections.reverse(list2);
int index = 0;
for(int i=m-1;i<n-1;i++){
int num = list2.get(index);
list.set(i,num);
index++;
}
ListNode temp = null;
ListNode res = null;
for(int i=0;i<list.size();i++){
int num = list.get(i);
ListNode node = new ListNode(num);
if(i == 0){
temp = node;
res = temp;
} else {
temp.next = node;
temp = node;
}
}
return res;
}
编辑于 2024-02-28 21:36: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) {
// write code here
if (m == n) {
return head;
}
int c = Math.min(m, n);
int f = Math.max(m, n);
n = f;
m = c;
int count = 1;
ListNode newTemp = null;
ListNode finalN = new ListNode(0);
ListNode cur = finalN;
while (head != null) {
if (count < m||count>n) {
cur.next = new ListNode(head.val);
cur = cur.next;
}
if (count >= m && count <= n) {
ListNode t1 = new ListNode(head.val);
t1.next = newTemp;
newTemp = t1;
}
if (count==n) {
while(newTemp!=null){
cur.next = new ListNode(newTemp.val);
cur=cur.next;
newTemp=newTemp.next;
}
}
head = head.next;
count++;
}
return finalN.next;
}
}
编辑于 2024-01-20 17:24:08
回复(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) {
if(m==n||head==null)return head;
ListNode go = head;
ListNode left=null;
ListNode right=null;
ListNode ll=null;
ListNode rr=null;
for(int i=1;i<m;i++){
ll=go;
go=go.next;
}
if(left==null)left=head;
go=head;
for(int i=1;i<=n;i++){
right=go;
go=go.next;
}
if(ll!=null)
left=ll.next;
if(right!=null)
rr=right.next;
ListNode pre=null;
ListNode t = left;
while(left!=rr){
ListNode temp = left.next;
left.next=pre;
pre=left;
left=temp;
}
left=t;
if(left!=null)
left.next=rr;
if(ll!=null)
ll.next=right;
if(ll==null)return right;
return head;
}
}
发表于 2023-12-14 17:21:10
回复(0)
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
