Leetcode 刷题 92. 反转链表 II

很多前端的同学对数据结构和算法这块没有太多的概念，很多leetcode的题目看不懂，有时候可能看了题解也不知道是什么意思。上一篇我们对链表的数据结构有了了解，下面根据题目来练习一下

92. 反转链表 II

题目

给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。

题解

我们首先来看看下这道题的意思是什么。这道题目其实很好理解，给你两个位置left和right,让你反转从位置left到位置right的链表节点。

这里还是需要一个虚拟头节点，然后我们需要计算出需要反转的个数n,以及需要反转的起点。

题目中我们就可以知道从位置 left 到位置 right 进行反转，那么需要反转的个数n就可以通过right-left+1计算得到。反转的起点，我们可以通过从头节点开始向后走，走到left的前一位就可以。下面用图来表示一下

我们看下代码：

// 定义一个哨兵元素
let ret = new ListNode(null, head)
// 最后需要返回的是ret 所以需要一个变量替换
let pre = ret
// 需要反转的个数
let n = right - left + 1
// 找到反转的起点
while (--left) {
    pre = pre.next
}

此时的pre就是反转的起点。剩下的就需要看看怎么反转了。从上篇文章Leetcode 刷题 206. 反转链表可以知道如何反转一个链表了。那现在反转的起点和需要反转的个数我们都已经知道，只需要对上篇文章的代码稍微修改一下就好了。

var reverse = function (head, n) {
    let prev = null, cur = head
    while (n--) {
            [cur.next, prev, cur] = [prev, cur, cur.next]
    }
    // head此时已经变成了最后一个节点了， 所以他需要指向下一位，此时下一位是cur
    head.next = cur
    return prev
}

这里我们前6行的代码只需要将之前的循环条件改为n--就好了，因为需要反转n次。注意看第7行，当链表反转完毕之后，head已经是最后一个节点了，所以head的next节点需要指向下一位

如图，首先将需要反转的节点单独处理，反转完毕之后，head的节点其实已经是最后一个了，只需要将head的next指向cur就可以串联起来了。目前图中可以看到，反转后的那一段还有头需要连接

我们只需要在将pre的next节点指向反转后的节点就好了。
下面看下完整代码：

var reverseBetween = function (head, left, right) {
    // 定义一个哨兵元素
    let ret = new ListNode(null, head)
    // 最后需要返回的是ret 所以需要一个变量替换
    let pre = ret
    // 需要反转的个数
    let n = right - left + 1
    // 找到反转的起点
    while (--left) {
        pre = pre.next
    }
    // 找到起点后开始反转
    pre.next = reverse(pre.next, n)
    return ret.next
};


var reverse = function (head, n) {
    let prev = null, cur = head
    while (n--) {
        [cur.next, prev, cur] = [prev, cur, cur.next]
    }
    // head此时已经变成了最后一个节点了， 所以他需要指向下一位，此时下一位是cur
    head.next = cur
    return prev
}

欢迎大家点赞评论，大家一起学习一起进步！！！

原文链接：https://juejin.cn/post/7332668127530909733 作者：翰玥