算法挑战: 链表

题目	难度	解法	考察点	链接	解法链接
203. 移除链表元素	简单	单指针	链表	203
141. 环形链表	简单	快慢指针	链表、双指针	141
206. 反转链表	简单	递归/迭代	链表	206
19. 删除链表的倒数第 N 个结点	中等	快慢指针	链表、双指针	19
21. 合并两个有序链表	简单	递归/迭代	链表、排序	21
876. 链表的中间结点	简单	快慢指针	链表、双指针	876
234. 回文链表	中等(easy)	快慢指针 + 栈/递归	链表、双指针	234	先双指针再翻转再比较
160. 相交链表	中等(easy)	双指针	链表、双指针	160
92. 反转链表-ii	中等	快慢指针	链表、双指针	92	找到位置后翻转，翻转完要清楚指针
142. 环形链表 II	中等	快慢指针 + 哈希表	链表、双指针、哈希	142	搞清距离公式
146. LRU缓存	困难	哈希表 + 双向链表	链表、哈希表	146

203. removeElements 函数

这个函数用于从链表中移除所有值为 val 的节点。

• 使用了一个哑节点（dummy node）来简化头节点的处理。
• 初始化一个 current 指针，从哑节点开始遍历。
• 当 current.next 的值等于给定的 val 时，通过 current.next = current.next.next; 来跳过并删除该节点。
• 否则，继续向下遍历。

返回时剔除哑节点，返回 dummy.next。

141. hasCycle 函数

这个函数用于判断一个链表是否包含环。

• 使用两个指针：slow 和 fast。
• slow 每次向前移动一个节点，而 fast 每次向前移动两个节点。
• 如果链表中有环，那么 slow 和 fast 指针最终会相遇。
• 如果 fast 到达链表末尾，说明链表没有环。

这两个函数分别解决了链表中的元素删除和环检测问题，使用了不同的遍历和指针操作技巧。希望这个总结能帮助你更好地理解这两个函数！

206 翻转链表

整个翻转过程依赖于三个指针：prev、current 和 next。

1. prev 用于跟踪当前节点（current）的前一个节点。
2. current 用于跟踪当前需要翻转的节点。
3. next 用于临时存储 current 的下一个节点，因为在翻转过程中 current.next 会被改变。

算法的核心步骤如下：

1. next = current.next 临时 。存储当前节点的下一个节点到 next。
2. current.next = prev 翻转。改变当前节点 current 的 next 指针，使其指向 prev，从而实现局部翻转。
3. prev = current 跟随。将 prev 更新为当前节点 current。跟随 current
4. current = next 移动。将 current 更新为 next，即向链表的末尾方向移动。

通过循环执行这些步骤，链表最终会完全翻转。

这个算法不仅直观，而且实现简单，时间复杂度是O(n)，其中 n 是链表的长度。希望这个总结能帮助你更好地理解这个问题！

21 合并两个有序链表

1. 初始化哑节点和当前指针：创建一个哑节点作为合并后链表的“虚拟”头节点，并使用一个当前指针（cur）来追踪新链表的最后一个节点。
2. 遍历两个链表：当两个输入链表 list1 和 list2 都不为空时，比较它们当前节点的值。
3. 节点添加与指针移动：
   • 如果 list1 当前节点的值大于 list2，则将 list2 当前节点添加到新链表的末尾，并将 list2 的指针向下移动。
   • 否则，将 list1 当前节点添加到新链表的末尾，并将 list1 的指针向下移动。
   • 在每次添加节点后，将 cur 指针移动到新链表的末尾。
4. 处理剩余节点：如果其中一个链表提前遍历完成，将另一个链表的剩余部分添加到新链表的末尾。
5. 返回结果：返回 dummy.next，因为 dummy 是哑节点，而 dummy.next 指向合并后的链表的实际头节点。

通过这种方式，你可以创建一个新的有序链表，它包含了两个输入链表的所有节点，同时也保持了排序。

876. 链表的中间结点

1. 初始化两个指针：slow 和 fast 都初始化为链表的头节点 head。
2. 开始遍历：只要 fast 指针和 fast.next 不为 null，继续遍历。
3. 移动指针：
   • slow 指针每次向前移动一个节点。
   • fast 指针每次向前移动两个节点。
4. 找到中间节点：当 fast 指针到达链表末尾或者无法再向前移动时，slow 指针就会指向链表的中间节点。
5. 返回结果：返回 slow 指针所指向的节点，即链表的中间节点。

该算法使用快慢指针的方法，fast 指针移动的速度是 slow 指针的两倍。因此，当 fast 到达链表的末尾时，slow 会位于链表的中间。

整体而言，这是一个非常有效的方法，时间复杂度为 O(n)，空间复杂度为 O(1)。希望这个总结能帮助你理解你自己写的代码！

19. 删除链表的倒数第 N 个结点

1. 初始化：创建一个哑节点并将其 next 指针指向链表的头节点。设置两个指针，fast 和 slow，并让它们都指向哑节点。
2. 移动 fast 指针：让 fast 指针先向前移动 n+1 步。
3. 同时移动 fast 和 slow：接下来，同时移动 fast 和 slow 指针，直到 fast 指针达到链表的末尾（null）。
4. 删除节点：此时，slow 指针将位于要删除的节点的前一个节点。通过改变 slow.next 的指向来删除该节点。
5. 返回结果：最后，返回哑节点的 next 指针，因为哑节点是我们为了方便操作而临时添加的。
   这样，我们就能在一趟遍历中删除链表中倒数第 n 个节点。希望这个总结能帮助你理解这道题！

234. 回文链表

这道题目要求判断一个单链表是否为回文结构。解题的主要步骤如下：

• 寻找中间节点：使用两个指针（fast 和 slow）来找到链表的中间节点。fast 指针每次移动两步，而 slow 指针每次移动一步。当 fast 指针到达链表末尾时，slow 指针会位于链表的中间。
• 反转后半部分：从 slow 指针开始，反转链表的后半部分。
• 检查是否为回文：从链表的头部和反转后半部分的头部开始，同时遍历并比较每个节点。如果所有节点都相等，那么链表就是一个回文。
• （可选）恢复链表：如果需要将链表恢复到原始状态，你需要再次反转其后半部分。

这个方法的时间复杂度是 O(n)，空间复杂度是 O(1)，符合题目的 Follow-up 要求。

160. 相交链表

主要目标是找到两个链表的交点。解题关键是使用两个指针，一个从第一个链表的头部开始，另一个从第二个链表的头部开始。

两个链表有相交，那么他们对接起来后最后几位肯定一样。

- 链表 A: a1 → a2 → c1 → c2 → c3 → null (长度 5)
- 链表 B: b1 → b2 → b3 → c1 → c2 → c3 → null (长度 6)


- a1 a2 c1 c2 c3 b1 b2 b3 c1 c2 c3
- b1 b2 b3 c1 c2 c3 a1 a2 c1 c2 c3

1. 首先，两个指针分别从各自的链表头开始遍历。
2. 当一个指针到达其链表的末尾时，将它重置到另一个链表的头部。
3. 如果两个链表相交，两个指针最终会在交点处相遇。

这种方法的优点是时间复杂度为 O(n)，空间复杂度为 O(1)。这里的 n 是两个链表中总节点数。

这样做的目的是让两个指针走过相同数量的节点，从而能在交点（如果存在）处相遇。

92. 反转链表-ii

1. 指针：您需要多个指针来跟踪列表的不同部分，例如子部分之前的最后一个节点，子部分内的第一个和最后一个节点以及子部分之后的节点。

2. 反转子部分：您可以使用标准的链表反转技术（交换相邻节点的“next”指针）来反转目标子部分中的节点。

3. 重新连接：在反转后，您需要正确地重新连接子部分之前的最后一个节点到子部分的新第一个节点，以及反转后的子部分的最后一个节点到其后面的第一个节点。

4. 虚拟节点：使用虚拟节点可以简化处理边缘情况，例如当(m)为1时。

5. 时间复杂度：此操作可以在(O(n))时间内完成，其中(n)是列表的长度，因为我们只需通过该列表进行一次遍历。

6. 空间复杂度：空间复杂度为(O(1))，因为我们只需要固定数量的指针。

最后返回 `dummy.next`，即整个链表的新头节点。

举例 12345 2,4 14325 而且我也知道 preStart.next.next = cur 是为了把 2后面接上5 preStart.next = prev 是为了把 1 后面接上4 但是我实在不能理解他是如何明确接的节点和位置。

这里的关键在于 `preStart.next` 和 `preStart.next.next` 这两个指针。

1. `preStart.next` 一直指向要翻转的子链表的第一个节点（在这个例子中是2）。即使这个子链表被翻转了，这个指针仍然会指向这个节点。
    
2. 当子链表（2,3,4）被翻转后，我们需要更新一下它与其他部分的连接。这就是 `preStart.next.next = cur` 和 `preStart.next = prev` 的作用。
    
3. `preStart.next.next = cur` 是将翻转子链表的最后一个节点（现在是2）连接到剩下的部分（5）。因为 `cur` 在循环结束后指向5。
    
4. `preStart.next = prev` 是将翻转子链表的第一个节点（现在是4）连接回主链表。因为 `prev` 在循环结束后指向4。

嗯好，我明白了第一步， preStart.next 一直指向2 所以 preStart.next.next 就是 2 的 next 要只想 5， 但是是怎么知道 cur 就是5的 因为上面的遍历吗。 第二个问题，当 2 的next 指向5后， 我需要把 1 preStart 的 next 指向4，我是怎么知道 prev 就是4

1. 关于 `cur`：在循环结束时，`cur` 指向子链表最后一个元素（这里是4）的下一个元素（这里是5）。这是因为在循环的最后一步，我们做了 `cur = next`，其中 `next = cur.next`。
    
2. 关于 `prev`：循环每次迭代都会更新 `prev`，使其指向当前翻转后的链表的第一个节点。因此，循环结束后，`prev` 会指向翻转子链表的第一个节点，这里就是4。
    

所以，这两个指针在循环结束后自然就位于我们希望他们所在的位置。这就是为什么 `cur` 和 `prev` 可以用于更新链表连接的原因。

142. 环形链表 II

通常使用Floyd的“乌龟和兔子”算法来解决。这个问题可以分为两个部分：

1. 首先，确定链表中是否存在环。可以使用两个速度不同的指针（通常称为slow和fast），slow每次移动一步，而fast每次移动两步。如果存在环，两个指针最终会在环内的某个位置相遇。

2. 找到环的起始节点。当两个指针相遇后，将其中一个指针重新放到链表的头部，然后两个指针以相同的速度（每次一步）前进。当它们再次相遇时，相遇点就是环的起始节点。

这个场景：

Head
  |
  v
O->O->O->...->O
               |
               v
               O   <--- Cycle Start
               |
               v
O<-------------O
^             /
|  (c-x)     /
|           /
|          /
|         /
|        /  (x)
|       /
|      /
v     v
O-----O   <--- Meeting point of slow & fast during the first phase

2(m+x) = m+x+nc, slow 走两倍m+x === fast 走 m+x 加 n倍的c
m+x = nc 如果 n = 1 那么 m = c-x


1. 画一个点，称之为 "Head"。
2. 从这个点画 \(m\) 个点（连在一起），把最后一个点标记为 "Cycle Start"。
3. 从 "Cycle Start" 画一个圈，包含 \(c\) 个点来表示环。
4. 标记 `slow` 和 `fast` 在环内相遇的点，距离 "Cycle Start" 有 \(x\) 个点。

现在：

- 第一阶段结束时，`slow` 在 \(m+x\) 位置，`fast` 在 \(m+x+nc\) 位置。
- 第二阶段开始时，把 `slow` 移动回 "Head"。

假设环的长度是 \(c\)，`slow` 和 `fast` 在环内相遇时，距离环的起点 \(x\) 步。所以 `fast` 距离环的起点还有 \(c-x\) 步。

现在，`slow` 从 "Head" 走 \(m\) 步到达 "Cycle Start"，同时 `fast` 也走 \(m\) 步，由于它距离 "Cycle Start" 是 \(c-x\)，两者加起来正好是一个环的长度 \(c\)，所以它们会在 "Cycle Start" 相遇。

1. 从`Head`到`Cycle Start`的距离为`m`。
2. `Cycle Start`就是环开始的地方。
3. 环内的点数为`c`。
4. 当`slow`和`fast`第一次在环内相遇时，他们之间的距离是`x`。
5. 环的其余部分（即从相遇点到`Cycle Start`）的距离是`c-x`。

在第二阶段，`slow`从`Head`开始，而`fast`从相遇点开始，它们都每次只走一步。当`slow`走了`m`步到达`Cycle Start`时，`fast`也正好走了`m`步，加上它原本距离`Cycle Start`的`c-x`步，总共走了`m + (c-x)`步，这正好是一个完整的环的长度，所以它们在`Cycle Start`处相遇。

希望这个“图”能帮助你理解这个问题！

146. LRU缓存

两个主要操作：

1. get(key): 获取指定 key 的值。如果 key 不存在，则返回 -1。
2. put(key, value): 插入或更新一个键值对。如果缓存达到了容量上限，需要移除最近最少使用的键值对。

解题思路：

1. 使用一个 Map 对象存储键值对。Map 保证了元素的插入顺序，这对于实现 LRU 算法很有帮助。
2. 为了跟踪缓存的容量，设定一个 capacity 变量。
3. 在 get() 方法中，如果 key 存在，返回对应的值并更新其在 Map 中的位置（把它移到最后）。
4. 在 put() 方法中，首先检查 key 是否已存在。如果存在，先删除旧的键值对。然后检查缓存是否满了，如果满了，移除最旧的（即最前面的）元素。最后，添加新的键值对。