剑指offer - 反转链表 - JavaScript
剑指offer - 反转链表 - JavaScript
心谭博客
发布于 2020-04-21 15:23:18
发布于 2020-04-21 15:23:18
题目描述：输入一个链表，反转链表后，输出新链表的表头。
题目描述
输入一个链表，反转链表后，输出新链表的表头。
解法 1: 借助栈
借助栈的后入先出的顺序，可以将顺序列表逆序。不过这不是原地反转，当然题目也没有要求。
处理过程如下：
- 从头到尾遍历链表，将节点 val 依次放入栈
- 从栈中依次取出 val，构造新节点，并连接节点
时间复杂度 O(N)，空间复杂度 O(N)。代码如下：
// ac地址：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
// 原文地址：https://xxoo521.com/2020-01-12-reverse-link/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (!head) {
return null;
}
const stack = [];
let node = head;
while (node) {
stack.push(node.val);
node = node.next;
}
const newHead = {
val: stack.pop(),
next: null
};
node = newHead;
while (stack.length) {
node.next = {
val: stack.pop(),
next: null
};
node = node.next;
}
return newHead;
};解法 2: 原地反转
“原地反转”的思路简单，但是实现起来有一些细节需要处理。链表类的原地操作，大部分都是细节上容易出错，导致死循环或者报错。
准备当前节点 node，和 node 的前一个节点 preNode。整体的思路如下：
- 保留当前节点的下一个节点
- 将当前节点的 next 指向前一节点 preNode
- 更新 preNode 为当前节点，更新当前节点为第一步保留的下一节点
- 判断当前节点是否是最后节点，如果不是，回到第一步；如果是，进入最后一步
- 将当前节点的 next 指向前一节点 preNode
时间复杂度是 O(N)，空间复杂度是 O（1）。代码如下：
// ac地址：https://leetcode-cn.com/problems/fan-zhuan-lian-biao-lcof/
// 原文地址：https://xxoo521.com/2020-01-12-reverse-link/
/**
* @param {ListNode} head
* @return {ListNode}
*/
var reverseList = function(head) {
if (!head) {
return null;
}
let node = head;
let preNode = null;
while (node.next) {
const nextNode = node.next;
node.next = preNode;
preNode = node;
node = nextNode;
}
node.next = preNode;
return node;
};本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2020-01-12，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录