链表 - 反转系列

来源：基础算法精讲 by 灵茶山艾府

题目	代码	备注
206. 反转链表	代码
92. 反转链表 II	代码
25. K 个一组翻转链表	代码
24. 两两交换链表中的节点	代码	*课后作业
445. 两数相加 II	代码	*课后作业
2816. 翻倍以链表形式表示的数字	代码	*课后作业

例题

206.反转链表

• 看注释的思考过程

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @return {ListNode}
 */
var reverseList = function(head) {
    //每个节点都存了next属性，这是一个地址，在图片里其实就是箭头，反转链表就是反转箭头，
    //比如1，2，3，反转过程：1的next指到null,2的next值到1，3的next指到2；
    //每次切换指向，涉及到的变量有current，previous，但是curr还需要遍历，所以要提前保存curr.next,同时注意pre也需要跟随curr遍历
    //最终，curr指到null，pre值到原来的尾，稍微想一下能想象出来
    let curr = head;
    let pre = null;

    while(curr){
        let nxt = curr.next;

        curr.next = pre;

        pre = curr;
        curr = nxt;
    }
    return pre;
};

92.反转链表二

• 看懂报错，去思考为什么，注意特殊情况
• 脑海里要有上一题反转链表的画面，清楚反转完的pre,curr,next指向哪里，多打印

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
    //局部反转，先把局部聚焦，看成整条反转，回想整条反转最后的指针curr，pre的位置，
    //可以发现结束后curr位置需要被left位置节点的next指过去，pre位置要被left左边的指过去
    //所以，这个left左边需要记录一下这个节点，
    //通常称之为 哑节点/哨兵节点


    //virtual node
    const dummy = new ListNode(0, head);
    let p0 = dummy;
    for (let i = 0; i < left - 1; i++) {
        p0 = p0.next;
    }
    let pre = p0;
    curr = p0.next;
    // console.log('curr', curr)
    //反转
    for (let i = 0; i < right - left + 1; i++) {
        let nxt = curr.next;
        //下面报错意思是只有一个节点的时候，为空，所以要引入虚拟头节点
        // Line 28 in solution.js
        //         let nxt = curr.next;
        //                        ^
        // TypeError: Cannot read properties of null (reading 'next')
        //     Line 28: Char 24 in solution.js (reverseBetween)
        //     Line 56: Char 19 in solution.js (Object.<anonymous>)
        curr.next = pre;
        pre = curr;
        curr = nxt;
    }

    p0.next.next = curr;
    p0.next = pre;//left指到反转链表的尾

    // console.log(p0, dummy,pre, curr)
    //注意，p0最终是left左边一位，dummy.next才是整个完整答案
    return dummy.next
};

k个一组翻转链表

• 参考上两题和注释
• 画图，一步一步来，这里的循环条件写法值得学习
• 注意p0节点的更新思路

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} head
 * @param {number} k
 * @return {ListNode}
 */

//k个一组进行反转，走一步看一步，pre，curr，nxt的位置，看起来是需要虚拟节点的

var reverseKGroup = function (head, k) {
    //统计节点个数技巧
    let n = 0;
    for (let tmp = head; tmp != null; tmp = tmp.next) n++;
    console.log('count', n)

    //v node
    const dummy = new ListNode(0, head);

    let p0 = dummy, pre = null, curr = head;

    for (; n >= k; n -= k) {
        for(let t = 0; t < k; t++){
            let nxt = curr.next;

            curr.next = pre;
            pre = curr;
            curr = nxt;
        }
        const tmp = p0.next;
        p0.next.next = curr;
        p0.next = pre;
        p0 = tmp;
    }
    return dummy.next;
};