算法 链表内指定区间反转

算法 链表内指定区间反转

/*
 * function ListNode(x){
 *   this.val = x;
 *   this.next = null;
 * }
 */

/**
  * 
  * @param head ListNode类 
  * @param m int整型 
  * @param n int整型 
  * @return ListNode类
  */
function reverseBetween( head ,  m ,  n ) {
    // 反转区间链表数组
    let arr = []
    // 创建新的链表头
    let newh = new ListNode(-1)
    newh.next = head
    let p = newh
    for(let i = 0; i < m - 1; i++){
        p = p.next
    }
    let p1 = p // m -1位置
    for(let i = 0; i <= n - m; i++){
        p = p.next
        arr.push(p)
    }
    let p2 = p.next // n + 1位置
    while(arr.length){
    	// 通过pop()方法弹出最后一个进行反转
        const n = arr.pop()
        p1.next = n
        p1 = p1.next
    }
    p1.next = p2
    return newh.next
}
module.exports = {
    reverseBetween : reverseBetween
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42