关于算法:206反转链表-算法leetcode附思维导图-全部解法300题

零 题目：算法（leetcode，附思维导图 + 全副解法）300 题之（206）反转链表

一 题目形容

二 解法总览（思维导图）

三 全副解法

1 计划 1

1)代码：

// 计划 1“本人。化归法”。// 技巧：“化归法，将不相熟 转换成 相熟的。个别咱们将链表转换成数组模式去存储，题目就会变得很好做（注：但面试官可能会不太称心！！）”。// 思路：// 1）边界：若 为空链表，间接返回 null。// 2）状态初始化：resList = [], resHead = head。// 3）外围 1：遍历链表，将链表上的值存入 数组 resList 中。// 4）外围 2：逆序遍历 resList，顺次将至更新值 head.val 中。// 5）返回后果：resHead。var reverseList = function(head) {
    // 1）边界：若 为空链表，间接返回 null。if (!head) {return null;}

    // 2）状态初始化：resList = [], resHead = head。let resList = [],
        resHead = head;

    // 3）外围 1：遍历链表，将链表上的值存入 数组 resList 中。while(head){resList.push(head.val);
        head = head.next;
    }

    // 4）外围 2：逆序遍历 resList，顺次将至更新值 head.val 中。const l = resList.length;
    head = resHead;
    index = l - 1;
    while (index >= 0) {head.val = resList[index];
        index--;
        head = head.next;
    }
    
    // 5）返回后果：resHead。return resHead;
};

2 计划 2

1)代码：

// 计划 2“本人。递归法”。// 注：“链表构造的特殊性，一些题目能够应用帝归去解。—— 数据结构与解法相适应”。// 思路：// 1）递归进口
// 注：若 以后链表的节点数 <2 个时，则 间接返回头结点 head 即可！// 2）递归主体
// 2.1）先反转前面的节点
// 2.2）前面的反转完了，再反转 head.next。// 2.3）最初反转 head。// 2.4）最初返回后果节点 resHead。var reverseList = function(head) {
    // 1）递归进口
    // 注：若 以后链表的节点数 <2 个时，则 间接返回头结点 head 即可！if (head === null || head.next === null) {return head;}

    // 2）递归主体
    // 2.1）先反转前面的节点
    const resHead = reverseList(head.next);
    // 2.2）前面的反转完了，其次反转 head.next。head.next.next = head;
    // 2.3）而后反转 head。head.next = null;
    // 2.4）最初返回后果节点 resHead。return resHead;
}

3 计划 3

1)代码：

// 计划 3“本人。迭代法”。// 1）状态初始化：pre = null, cur = head。// 2）外围：循环解决，条件是 当 cur 为真值时。// 2.1）外围：上面 4 行，说白了，就是解决 cur.next, pre, cur 3 者的关系！// 即 [cur.next, pre, cur] = [pre, cur, cur.next]。// 注：下面 4 行等价于上面 1 行，然而下面的性能好很多！// [cur.next, pre, cur] = [pre, cur, cur.next];

// 3）返回后果节点 pre。var reverseList = function(head) {
    // 1）状态初始化：pre = null, cur = head。let pre = null,
        cur = head;

    // 2）外围：循环解决，条件是 当 cur 为真值时。while (cur) {
        // 2.1）外围：上面 4 行，说白了，就是解决 cur.next, pre, cur 3 者的关系！// 即 [cur.next, pre, cur] = [pre, cur, cur.next]。const next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
        // 注：下面 4 行等价于上面 1 行，然而下面的性能好很多！// [cur.next, pre, cur] = [pre, cur, cur.next];
    }

    // 3）返回后果节点 pre。return pre;
}

四 资源分享 & 更多

1 历史文章 – 总览

2 博主简介

码农三少，一个致力于编写 极简、但齐全题解（算法 ）的博主。
专一于 一题多解、结构化思维，欢送一起刷穿 LeetCode ~