文章目录加载中
反转链表
# 1. 题目描述
定义一个函数,输入一个链表的头结点,反转该链表并输出反转后链表的头结点。
# 2. 思路描述
思路一:经典的“链表头插法”,时间复杂度是 $O(N)$,但是空间复杂度也是 $O(N)$
思路二:链表原地操作,时间复杂度是 $O(N)$,但是空间复杂度只有 $O(1)$。
- 保存当前节点
node
的上一个节点pre
- 节点
node
的next
指向pre
- 分别将
pre
和node
向后移动 1 个位置
- 如果
node
为 null,链表翻转完毕,此时pre
指向新的头节点,返回即可 - 否则,回到第 1 步继续执行
# 3. 代码实现
/**
* 节点定义
*/
class Node {
constructor(value, next) {
this.value = value;
this.next = next;
}
}
/**
* 翻转链表
* @param {Node} head 未翻转链表的头节点
* @return {Node} 翻转链表后的头节点
*/
function reverseList(head) {
let node = head,
pre = null;
while (node) {
let next = node.next;
node.next = pre;
pre = node;
node = next;
}
return pre;
}
/**
* 以下是测试代码, 分别输出倒数第2、3和5个节点
*/
let node3 = new Node(3, null),
node2 = new Node(2, node3),
node1 = new Node(1, node2),
head = new Node(0, node1);
let newHead = reverseList(head);
while (newHead) {
console.log(newHead);
newHead = newHead.next;
}
本文来自心谭博客:xin-tan.com,经常更新web和算法的文章笔记,前往github查看目录归纳:github.com/dongyuanxin/blog