06、链表（上）

思考：使用链表如何实现 LRU 缓存淘汰算法?

主要内容

缓存：一种提高数据读取性能的技术，各领域广泛运用：浏览器缓存、CPU 缓存、数据库缓存。

当缓存空间不够时，会采用缓存淘汰策略来清除一些数据。常用的缓存淘汰策略为：
先进先出策略 FIFO(First In First Out)、最少使用策略 LFU(Last Frequently Used)、最近最少使用策略 LRU(Last Recently Used)

链表可通过“指针”将零散的内存块串起来。
链表的插入、删除操作为 O(1)；查询操作为 O(n)

常见的链表结构如下：

空间换时间：当内存空间充足时，则可以使用空间复杂度高、时间复杂度底的算法或数据结构来提升代码的执行速度；反之亦然。

而缓存就是“空间换时间”的运用，正常情况下数据存储在硬盘中占用空间小，但每次查找都要访问一次硬盘，比较耗时；所以就将数据存储在内存中，虽然占用了内存空间，但每次数据查询速度就很快。

解答思考

思考：使用链表如何实现 LRU(最近最少使用策略) 缓存淘汰算法?

思路：

• 维护一个有序的单链表结构，越后面是越早访问的数据。
• 插入一个新数据时，有以下情况：
  • 若已在链表中，则找到它原来的位置删除掉，然后再最前面添加它
  • 若不在链表中，则又分为两种情况：
    • 缓存已满：删除最末尾的，再将其添加到最前面
    • 缓存未满：直接将其添加到最前面

由于链表的查找始终都需要遍历一遍的，所以缓存访问的时间复杂度为 O(n)

新的思考

如何利用数组实现 LRU 缓存淘汰策略呢？

思路还是类似的：

• 维护一个数组，越后面是越早访问的数据。
• 插入一个新数据时，有以下情况：
  • 若已在数组中，则找到它原来的位置删除掉(后面的往前移一位)，然后再最前面添加它
  • 若不在数组中，则又分为两种情况：
    • 缓存已满：删除最末尾的，再将其添加到最前面
    • 缓存未满：直接将其添加到最前面

如何判断一个字符串是否是回文字符串？

回文字符串：从左往右和从右往左读都是一样的，比如 “level”、“racecar”和“12321”
核心思路：找到中心位置 n，n-1 与 n+1 位置上的字符串始终相等

如果字符串是采用单链表结构，那又该如何判断呢？
思路： 采用快慢两个指针，快指针每次跳两个，慢指针每次跳一个，找到中心点，在找的过程中将前半段反序。
当找到中心点后，慢指针指向的是[单数字符串的中心点]（单数只有一个中心点）或[双数字符串的中心点 2]（双数有两个中心点）
然后再分别向后对比[前半段反序字符串]与[后半段正序字符串]中的每一个是否相等

// 伪代码演示
function isPalindrome(ListNode) {
  let fast = ListNode.head
  let slow = ListNode.head
  let prev = null

  // 找中心点+前半段反序
  while(fast && fast.next) {
    fast = fast.next.next // 快指针跳两个
    const next = slow.next // 慢指针下一个指向的，暂存下

    // 反序操作
    // 第一次时，head 的 next 指向 null 了
    // 第二次时，第二个字符串的 next 指向第一个
    // .....以此类推实现反序
    slow.next = prev
    prev = slow // 暂存反序的下一个

    slow = next // 慢指针跳一个
  }

  // 当上述 while 指向完毕时，prev 指向反序字符串的 head
  // slow、fast 可能的情况如下：
  // str1: goog, fast -> null, slow -> o(中心点2), prev -> o(中心点1)
  // str2: adbhfhbda, fast -> a(最后一个), slow -> f(中心点), prev -> h(中心点前一个)
  // 可以发现字符串的奇偶决定了 slow 的位置

  // 现在构建了一个前半段反序的字符串链表，prev 指向该字符串的 head
  // 然后还有个后半段正序的字符串链表，slow 指向该字符串的 head 或 head 前一个

  if(fast) {
    // 当 fast 还有值(字符串为奇数时)
    // 则主动将 slow 后移一位用于指向[后半段正序]的 head
    slow = slow.netx
  }

  // [前半段反序字符串]与[后半段正序字符串]中的每一个是否相等
  while(slow) {
    if(slow.value !== prev.value) return false

    slow = slow.next // [后半段正序字符串]后移一位
    prev = prev.next // [前半段反序字符串]后移一位
  }

  return true

}