leetcode 92.反转链表II dummy节点的应用

题目

方法

dummy节点

链表的第一个结点，因为没有前驱结点，存在同时删除前驱和后继的情况，这时候我们需要人为构造dummy节点——人为制造出来的第一个结点的前驱结点，也就是说，在可能操作head节点时，我们可以创建dummy节点来解决

code

var reverseBetween = function(head, left, right) {
    let dummy = new ListNode()
    dummy.next = head

    let p = dummy
    let pre, cur, leftHead

    for(let i=0; i<left-1; i++){
        p = p.next
    } 

    // leftHead缓存反转区间的前驱节点, 后面我们需要使用leftHead连接翻转区间翻转后的第一个节点
    // 以题干图示为例, 此时leftHead缓存了节点1
    leftHead = p

    // start缓存反转区间的第一个节点, 区间翻转后他是最后一个节点, 我们要用他连接翻转区间的后继节点
    // 以题干图示为例, 此时start缓存了节点2
    let start = leftHead.next
    pre = start
    cur = pre.next

    for(let i=left; i<right; i++){
        let next = cur.next
        cur.next = pre
        pre = cur
        cur = next
    }
    // 反转区遍历结束后, pre指针停在反转区最后一个节点

    // 以题干图为例, 节点1是当前的leftHead, 此时pre是节点4, 此步使 1 --> 4
    leftHead.next = pre

    // 以题干图为例, 节点2是当前的start, 此时cur是节点5, 此步使 2 --> 5
    start.next = cur

    return dummy.next
}
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