重启DAY4 翻转链表

跟着灵茶山艾府大佬学习算法思路的day4，目标是在一个月内掌握hot100

b站链接如下：

反转链表【基础算法精讲 06】

反转链表 题目描述：

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

示例 1：

输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]

示例 2：

输入：head = [1,2]
输出：[2,1]

示例 3：

输入：head = []
输出：[]

思路：

用pre，cur，next分别记录上一个节点，目前的节点和下一个节点，next节点便于将指向下一个节点的指针指向上一个节点，同时不丢失下一个节点的信息。

代码：

var reverseList = function(head) {
    let pre = null;
    let cur = head;
    while (cur) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    return pre;
};

总结：

看了灵神的力扣题解，这种思路是头插法（每次被插入新链表的节点都成为新链表的头结点），还有一种思路是尾插法：

递归递归，有递有归。

我们先「递」到链表的末尾节点，作为新链表的头节点。然后在「归」的过程中，一个一个地把节点插在新链表的末尾。

新链表的末尾节点在哪？就是当前节点的 next。具体实现如下。

// 首先「递」到链表末尾，把末尾节点作为新链表的头节点 revHead
// 然后在「归」的过程中，把经过的节点依次插在新链表的末尾（尾插法）
var reverseList = function(head) {
    // 判断 head === null 是为了兼容一开始链表就是空的情况
    if (head === null || head.next === null) {
        return head; // 链表末尾，即下面的 revHead
    }
    const revHead = reverseList(head.next); // 「递」到链表末尾，拿到新链表的头节点
    const tail = head.next; // 在「归」的过程中，head.next 就是新链表的末尾
    tail.next = head; // 把 head 插在新链表的末尾
    head.next = null; // 如果不写这行，新链表的末尾两个节点成环，这俩节点互相指向对方
    return revHead;
};

反转链表 II 题目描述：

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

示例 1：

输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]

示例 2：

输入：head = [5], left = 1, right = 1
输出：[5]

思路：

这道题相较第一题，要求的是翻转链表内的部分元素，而其他元素保持原序，那么就需要利用到在翻转链表时出现的一个性质。

此时引入一个p0节点的概念，即翻转段的上一个节点，根据p0和p0.next，就能锁定迭代完成后翻转段的最后一个节点和翻转段紧接的下一个无需修改的节点。

考虑到存在翻转段从第一个节点开始的情况，可以在head前面添加一个哑结点。这样可以一直保证存在p0，也便于返回头结点（第一个节点开始的翻转会导致头结点发生变化）。

在具体实现的时候，还需要考虑p0和翻转段的链接关系。在翻转段翻转后，p0.next和反转链表的最后一个节点是同一个节点，而翻转段断开后右边的第一个节点此时实质上是断开的，但由于循环中cur指向了这个节点，因此可以通过cur来重新连接整个链表。因此在最后要补充cur和pre的链接。

这是灵神的解题思路，可以称为反转后再接回原链表。

再附一张评论区兄弟的示意图：

其实还有一种头插法的思路，保持cur始终指向一开始left指向的节点（保持指向的节点不变，但该节点所处的位置会一直变化），pre始终指向left-1所处的节点（也是保持指向的节点不变，但因为left-1这个节点不会进行位置更改，因此是位置与节点都不会）。每次都将cur的下一个节点插入到pre的前面，相当于在一个子链表中不断实现头插。

代码：

灵神的思路：

var reverseBetween = function(head, left, right) {
    const dummy = new ListNode(0, head);
    let p0 = dummy;
    for (let i = 0; i < left - 1; i++) {
        p0 = p0.next;
    } // 找到p0位置
    let pre = null;
    let cur = p0.next;
    for (let i = 0; i < right - left + 1; i++) {
        const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next; // 这部分和第一题一样
    }
    p0.next.next = cur; // 接回原链表的过程
    p0.next = pre;
    return dummy.next;
};

头插法：

var reverseBetween = function(head, left, right) {
    let dummy = new ListNode(0, head); // 哨兵节点，处理 left=1 的情况
    let pre = dummy;

    // 1. 走到 left-1 的位置
    for (let i = 0; i < left - 1; i++) {
        pre = pre.next;
    }

    let cur = pre.next; // cur 始终指向 left 位置的节点（不动）

    // 2. 头插法：把 cur.next 逐个插到 pre 后面
    for (let i = 0; i < right - left; i++) {
        let next = cur.next; // 要插的节点
        cur.next = next.next; // cur 跳过 next
        next.next = pre.next; // next 指向 pre 的下一个
        pre.next = next; // pre 指向 next
    }

    return dummy.next;
};

总结：

头插思路也不难理解，灵神的思路是在第一道题的反转思路上演化的，所以最后针对这道题还要打一个插回原链表的补丁。而头插法的思路是基于这道题设计的，和第一题的翻转思路差异就更大一些。这道题难度不大但思路巧妙，两种思路都值得好好回味一下。

要做这类链表反转的题，最好还是手边备好纸笔，在做的时候动手画图模拟一下中间状态的节点的指向情况，靠脑补确实还挺难想象的，因为链表虽然物理实际上具有空间顺序，但使用时是根据逻辑顺序，不通过动笔记录节点变化（在纸上的节点无论如何都具备一定的空间顺序，除非模拟一步就重排顺序，但这样不易于理解链表的空间顺序不变性），其实不易于理解这种空间和逻辑的矛盾性。

除了空间/逻辑矛盾，链表题还有一个难点是操作的中间状态很难可视化——

数组操作完一步，你还能看到完整的数组；链表改了一个 next，整个结构就变了，而且你脑子里很难同时追踪三四个指针的状态。

这也是为什么链表题画图比写代码更重要，先把每一步的指针变化画清楚，代码反而是最后一步。

K 个一组翻转链表 题目描述：

给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。

k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

示例 1：

输入：head = [1,2,3,4,5], k = 2
输出：[2,1,4,3,5]

示例 2：

输入：head = [1,2,3,4,5], k = 3
输出：[3,2,1,4,5]

思路：

解答这道题首要的关键，是要留意到成组翻转的办法其实就是将上一题翻转部分链表的操作重复多次，在每次之中要重置p0或者pre和cur的指向，使这些指针指向新的未处理的组别。

其次要考虑边界条件，如果链表节点总数不足k，就直接返回。

满足可翻转条件时，对于每一组翻转的处理是可以和上一题一样的，唯一需要多做的一件事就是将p0更新成下一段要翻转的链表的上一个节点，那么在一组节点翻转完毕时，那个所谓的上一个节点就是翻转组的最后一个节点，此时也仍是p0指向的节点。

所以可以在将这个翻转组接回原链表之前，可以暂存p0.next，这样接回后直接将p0更新为p0.next即可。

最后的实现思路类似上一题，也有两种，反正把上一题的核心思路包装进这题分组的壳子里去就行。灵神的思路在题解中有，我就用头插法的思路来实现。

代码：

头插法思路：

var reverseKGroup = function(head, k) {
    const dummy = new ListNode(0, head);
    let n = 0;
    let cnt = head;
    while (cnt) { // 判断总数
        n++;
        cnt = cnt.next;
    }
    let cur = head;
    let pre = dummy;

    while (n >= k) { // 反转链表2 头插法
        for (let i = 0; i < k - 1; i++) {
            let next = cur.next; // 要插的节点
            cur.next = next.next; // cur 跳过 next
            next.next = pre.next; // next 指向 pre 的下一个
            pre.next = next; // pre 指向 next
        }
        pre = cur; // 指向新组别
        cur = cur.next;
        n -= k; // 缩小总数

    }
    return dummy.next;
}

灵神的思路：

var reverseKGroup = function(head, k) {
    // 统计节点个数
    let n = 0;
    for (let cur = head; cur; cur = cur.next) {
        n++;
    }

    const dummy = new ListNode(0, head);
    let p0 = dummy;
    let pre = null;
    let cur = head;

    // k 个一组处理
    for (; n >= k; n -= k) {
        for (let i = 0; i < k; i++) { // 同 92 题
            const nxt = cur.next;
            cur.next = pre; // 每次循环只修改一个 next，方便大家理解
            pre = cur;
            cur = nxt;
        }

        // 见视频
        const nxt = p0.next;
        p0.next.next = cur;
        p0.next = pre;
        p0 = nxt;
    }
    return dummy.next;
};

总结：

在上一题的基础上，能够理解灵神所说的更换p0的分组思路，这题就不太难，本质上最难的地方还是完成链表指针的更新模拟。