Review
- 2021/06/09
- 2024-09-09 07:51
[!Summary]
一、Introduction #
数组需要一块连续的内存空间来存储，对内存的要求比较高。 链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用。
4种最常见的链表结构，它们分别是：
- 单链表
- 双向链表
- 循环链表
- 双向循环链表
常见问题 #
如果字符串是通过单链表来存储的，那该如何来判断是一个回文串呢？
快慢指针定位中间节点
从中间节点对后半部分逆序
前后半部分比较，判断是否为回文
后半部分逆序复原
反转链表
- 反转单向链表
- 反转双向链表
合并两个有序链表
- 合并两个有序链表,生成一个新的有序链表
检测链表中是否有环
- 使用快慢指针检测链表中是否有环
- 找出环的入口点
删除链表中的节点
- 给定一个节点,删除该节点
- 给定一个值,删除链表中所有值等于该值的节点
找出链表的中间节点
- 使用快慢指针找出链表的中间节点
删除链表的倒数第N个节点
- 给定一个整数N,删除链表的倒数第N个节点
旋转链表
- 将链表向右旋转k个位置
奇偶链表重排
- 将一个链表的奇数节点和偶数节点分离,然后重新串联起来
扁平化多级双向链表
- 将多级双向链表扁平化为单级双向链表
两数相加(链表版)
- 给定两个非空链表,它们表示两个非负整数。将这两个整数相加,并以链表形式返回结果。