site logo

Marico' space

链表内指定区间反转

算法解析 2024-06-13 08:54:34 224

描述

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 �(�)O(n),空间复杂度 �(1)O(1)。

例如:

给出的链表为 1→2→3→4→5→NULL, m=2,n=4,

返回 1→4→3→2→5→NULL.

数据范围:链表长度 0<size≤10000<mnsize,链表中每个节点的值满足 |val| ≤1000

要求:时间复杂度 O(n) ,空间复杂度O(n)

进阶:时间复杂度O(n),空间复杂度O(1)

示例一

输入:{1,2,3,4,5},2,4

返回值:{1,4,3,2,5}

示例二

输入:{5},1,1

返回值:{5}

测试通过答案:

/* @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
  */
function reverseBetween( head ,  m ,  n ) {
    // write code here
    var cur=head;
    var st=[];
    var count=1;
    while(cur){
        if(count>=m&&count<=n){
            st.push(cur.val);
        }
        cur=cur.next;
        count++;
    }
    cur=head;
    count=1;
    while(cur){
        if(count>=m&&count<=n){
            cur.val=st.pop();
        } else {
          if(count>n)  break
        }
        cur=cur.next;
        count++;
    }
    return head;
}
module.exports = {
    reverseBetween : reverseBetween
};