怎么用ftp备份网站,管家婆crm,网站开发能做什么,全景网站怎么做描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转#xff0c;要求时间复杂度 O(n)O(n)#xff0c;空间复杂度 O(1)O(1)。 例如#xff1a; 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m2,n4 返回 1→4→3→2→5→NULL
数据范围#xff1a; 链表…描述
将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转要求时间复杂度 O(n)O(n)空间复杂度 O(1)O(1)。 例如 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m2,n4 返回 1→4→3→2→5→NULL
数据范围 链表长度 0size≤100000m≤n≤size链表中每个节点的值满足 ∣val∣≤1000
要求时间复杂度 O(n) 空间复杂度 O(n)
进阶时间复杂度 O(n)空间复杂度 O(1)
示例1
输入
{1,2,3,4,5},2,4
返回值
{1,4,3,2,5}示例2
输入
{5},1,1
返回值
{5}
思路分析
这里是反转对应区间所以可以一个一个进行反转比如示例1里面反转2到4这个区间
可以先将其变成1-3-2-4-5然后再变成1-4-3-2-5
演变过程 代码
import java.util.*;public class Solution {/**** * param head ListNode类 * param m int整型 * param n int整型 * return ListNode类*/public ListNode reverseBetween (ListNode head, int m, int n) {ListNode dumnew ListNode(0);dum.nexthead;ListNode predum;for(int i1;im;i){prepre.next;// 找到m的上一个节点}headpre.next;// 从m的位置开始进行交换ListNode next;// 用于暂存遍历节点的后继节点for(int im;in;i){// 暂存遍历节点的下一个节点nexthead.next;// 让当前节点指向 后继节点的后继节点head.nextnext.next;// 让后继节点指向反转元素的首位next.nextpre.next;// 让m的上一个节点 指向 此后继节点pre.nextnext;}return dum.next;}
}
