206.反转链表
给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
示例 2：
输入：head = [1,2]
输出：[2,1]
示例 3：
输入：head = []
输出：[]
提示：
链表中节点的数目范围是 [0, 5000] -5000 <= Node.val <= 5000
进阶： 链表可以选用迭代或递归方式完成反转。你能否用两种方法解决这道题？
解法一：递归
这道题算是一道简单的题，我使用递归的方法却难倒我自己了，代码如下：
/**
* 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) {
const reverseListHelper = (node) => {
if (node === null || node.next === null) {
return node;
}
const temp = reverseListHelper(node.next);
node.next = null;
temp.next = node;
return temp;
};
return reverseListHelper(head);
};
思路： 按照我的思路，一直递归到最后一个节点，并将它作为 temp 返回，然后最后一个节点作为 head 节点， head.next 就接上一个节点，于是就 temp.next = node;, 却不知道这行代码一直在修改新的头节点的 next 值，导致最后返回的只有原始链表的 [tail, head]
所以， temp.next = node; 这行代码是罪魁祸首！
然后我改成这样下面这样
/**
* 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) {
const reverseListHelper = (node) => {
if (node === null || node.next === null) {
return node;
}
const temp = reverseListHelper(node.next);
node.next = null;
node.next.next = node;
return temp;
};
return reverseListHelper(head);
};
很明显发现，node.next = null; 赋值之后， 下面这行就报错了 node.next.next = node, null.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
* @return {ListNode}
*/
var reverseList = function (head) {
const reverseListHelper = (node) => {
if (node === null || node.next === null) {
return node;
}
const temp = reverseListHelper(node.next);
node.next.next = node;
node.next = null;
return temp;
};
return reverseListHelper(head);
};
来！看看结果！
解法二：栈
/**
* 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) {
const stack = [];
while (head != null) {
stack.push(head);
head = head.next;
}
if (!stack.length) {
return null;
}
let node = stack.pop();
const newHead = node;
while (stack.length) {
const temp = stack.pop();
node.next = temp;
node = node.next;
}
node.next = null;
return newHead;
};
解法三：双链表
说实话， 这种思路很不好理解，并且实测效率不高;
思路：
原始链表迭代的时候，每一个节点作为新链表的头结点。
/**
* 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) {
let newHead = null;
while (head != null) {
let temp = head.next;
head.next = newHead;
newHead = head;
head = temp;
}
return newHead;
};