leetcode-链表类题目

链表（Linked List）

• 定义：链表（Linked List）是一种线性表数据结构，他用一组任意的存储单元来存储数据，同时存储当前数据元素的直接后继元素所存放的内存地址。
• 操作
  • 插入和删除操作时间复杂度为O(1)
  • 随机访问第k个元素的时间复杂度为O(n)
• 单链表：
  • 实现：数据域data+指针域next
• 循环链表：
  • 实现：尾结点指针指向头结点
  • 优点：支持时间复杂度O(1)找到头结点
• 双向链表：
  • 实现：数据域data+指针域prior和next
  • 优点：支持时间复杂度O(1)找到前驱结点
• 数组VS链表
  • 时间复杂度
    • 数组随机访问O(1)，插入删除O(n)
    • 链表随机访问O(n)，插入删除O(1)
  • 访问效率
    • 数组使用连续内存空间实现，可以借助CPU缓存机制预读数据，访问效率更高；
    • 链表在内存中非连续存储，对CPU缓存不友好，无法有效预读
  • 空间
    • 数组大小固定，声明时需要指定其大小，可能出现内存不足或者浪费情况
    • 链表天然支持动态扩容，没有空间浪费情况
• 应用：使用链表实现LRU缓存淘汰算法
  • 缓存：一种提高数据读取性能的技术，广泛应用于硬件设计，软件开发，如CPU缓存，数据库缓存，浏览器缓存。缓存大小有限，当缓存满时，需要使用缓存淘汰策略决定哪些数据被清理，哪些数据被保留
  • 缓存淘汰策略指当缓存满时数据的清理顺序，包括先进先出策略（FIFO），最少使用策略(Least Frequently Used, LFU)，最近最少使用策略(Least Recently Used, LRU)
  • 维护一个有序单链表，当有新的数据被访问时，从链表头开始遍历链表：
    1. 若链表中存在新数据，将其删除，插入到链表头
    2. 若链表中不存在新数据：
       • 若缓存未满，将新数据插入到链表头
       • 若缓存已满，删除链表尾结点，将新数据插入到链表头
• 链表代码书写的注意事项：
  • 警惕指针丢失和内存泄漏
    • 插入节点时，注意操作顺序
    • 删除链表结点时，手动释放内存空间
  • 利用哨兵简化实现难度
    • 针对链表的插入和删除操作，需要对插入第一个结点和删除最后一个节点的情况进行特殊处理
    • 引入头结点，将head指针始终指向头结点，头结点指向第一个数据节点
  • 边界条件处理
    • 链表为空时
    • 链表只包含一个节点时
    • 链表只包含两个节点时
    • 操作头结点和尾结点时
  • 举例画图，辅助思考
• 5个常见的链表操作
  • 单链表反转（分别使用迭代和递归实现）
  • 链表中环的检测（迭代实现和快慢指针实现）
  • 两个有序的链表合并（常规解法和递归解法）
  • 删除链表倒数第n个结点（单指针两次遍历和双指针一次遍历）
  • 求链表的中间节点（单指针两次遍历和双指针一次遍历）