206、反转链表|206、反转链表 | 算法（leetcode，附思维导图 + 全部解法）300题 206、反转链表|算法（leetcode，

零标题：算法（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 历史文章 - 总览