反转单向链表 #

题目 #

定义一个函数，输入一个单向链表的头节点，反转该链表，并输出反转之后的头节点

链表 #

链表是一种物理结构（非逻辑结构），是数组的补充。
数组需要一段连续的内存空间，而链表不需要。

数据结构

• 单向链表 { value, next }
• 双向链表 { value, prev, next }

两者对比

• 链表：查询慢，新增和删除较快
• 数组：查询快，新增和删除较慢

应用场景 #

React Fiber 就把 vdom 树转换为一个链表，这样才有可能随时中断、再继续进行。
如果 vdom 是树，那只能递归一次性执行完成，中间无法断开。

分析 #

反转链表，画图很好理解。没有捷径，遍历一边，重新设置 next 指向即可。
但实际写代码，却并不简单，很容易造成 nextNode 丢失。

因此，遍历过程中，至少要存储 3 个指针 prevNode curNode nextNode

时间复杂度 O(n)

答案 #

参考 reverse-link-list.ts

划重点 #

• 链表
• 链表和数组的不同
  • 内存占用
  • 查询、新增、删除的效率
• 如何保证 nextNode 不丢失

扩展 #

思考：用数组和链表实现队列，哪个性能更好？