木易

# Road Map

升级路线：

  • 查找链表位置：142 -> 160
  • 删除链表元素：203 -> 19 -> 237 -> 83
  • 重排链表：24 -> 86 -> 143 -> 148
  • 旋转链表：206 -> 61 -> 92
  • 合并链表：21 -> 23 ->
  • LRU 缓存设计：706 -> 146

# 链表

链表的题目一般细节比较多，我习惯于先在纸上画一下过程，理清楚思路，然后一步一步去编写代码实现；

# 解题技巧

  1. 巧用 dummpy，在头结点发生改变时，不需要考虑头结点的特殊处理，只要返回 dummpy.next 作为头结点即可
  2. 快慢指针，用于定位节点

# 查找链表元素

查找链表中的指定位置，一般会用到快慢指针的配合

比如：找环，找倒数第 K 个节点，找中间节点等等

# 删除链表元素

image-20220909234758799

一般涉及到删除操作，会考虑在开头增加辅助节点dummpy

这样就不需要考虑删除链表头的特殊情况的处理

# 翻转链表

image-20220909231525529

可能会翻转头节点，所以需要增加 dummpydummpy 节点；

旋转链表 一般常用的技巧：（以翻转链表下标 [left,right][left, right] 区间的节点为例 ）

1、 找到要旋转部分的前一个节点，记录 为 aa

2、对于每一对节点 bb，cc，进行翻转(需要借助 d = c.next) ；一共需要迭代 right−leftright - left 次

3、翻转完成后，处理 翻转区间的首尾指针； a.next.next = c, a.next = b

掌握上述技巧，相信遇到翻转链表的题目就不会再为难了(#^.^#)

力扣上的练习题目：

← 0x14_哈希 →