和数组不同的是，链表并不需要一块连续的内存空间，它可以通过指针将一组零散的内存块串联起来使用。链表的基本操作是最考验逻辑思维能力的，尤其需要注意：
- 指针/引用的含义
- 哨兵/保护结点作为访问入口
- 边界与异常检查
| 题目 | 备注 |
|---|---|
| 203. 移除链表元素 | 保护结点 |
| 206.反转链表 | 保护结点 |
| 707.设计链表 | 保护结点 |
| 25.K 个一组翻转链表 | 保护结点 |
| 24. 两两交换链表中的节点 | 保护结点 |
| 141.环形链表 | 快慢指针 |
| 142.环形链表 II | 快慢指针 |
| 19. 删除链表的倒数第 N 个结点 | 快慢指针 |
AC136.邻值查找：对序列\(A\)中每一个数\(A_i\)，求在\(A_i\)前的数与\(A_i\)的最小差值，以及对应下标（若最小差值对应下标不唯一，则返回最小下标）。例如，输入1, 5, 3, 4, 2，最小差值4, 2, 1, 1，对应下标1, 1, 2, 1。一个可能的想法是，对前\(i\)个数维护一个“有序”集合，二分查找该有序序列中\(A_i\)的前驱与后继，比较差值，返回最小差值与对应下标。
点击查看代码
import java.io.*;
import java.util.Map;
import java.util.TreeMap;
public class Main {
public static void main(String[] args) throws Exception {
StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
BufferedWriter br = new BufferedWriter(new OutputStreamWriter(System.out));
st.nextToken();
int n = (int) st.nval;
// 平衡树
TreeMap<Integer, Integer> map = new TreeMap<>();
for (int i = 1; i <= n; i++) {
st.nextToken();
int val = (int) st.nval;
// 添加关键字和对应的值，即数值与下标
map.put(val, i);
if (i != 1) {
// 返回大于等于 key 的最小元素
Map.Entry<Integer, Integer> up = map.ceilingEntry(val + 1);
// 返回小于等于 key 的最大元素
Map.Entry<Integer, Integer> down = map.floorEntry(val - 1);
int res = Integer.MAX_VALUE, pos = -1;
if (down != null) {
res = val - down.getKey();
pos = down.getValue();
}
if (up != null && up.getKey() - val < res) {
res = up.getKey() - val;
pos = up.getValue();
}
br.write(res + " " + pos);
br.newLine();
}
}
br.flush();
}
}