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;
};