力扣总结 数据结构（二）：链表

链表和数组是最基本的数据结构，是其他数据结构的基础。

链表和数组都是线性结构，但在内存中，数组的元素是连续的，而链表不是。 所以链表是把一些分离独立的元素按引用链接到一起。

链表能在 O(1) 时间插入、删除元素，但需要 O(N) 时间访问到元素，与数组相反。

python 中的内置库 deque 即是用双向链表实现的。

1 基础

1.1 设计

• 0707 设计链表

1.2 操作

• 0002 两数相加
• 0024 两两交换链表中的节点
• 0082 删除排序链表中的重复元素 II
• 0237 删除链表中的节点

2 进阶

2.1 操作

• 0061 旋转链表
• 0086 分隔链表
• 0328 奇偶链表
• 0725 分隔链表

2.2 快慢指针

• 0019 删除链表的倒数第 N 个结点
• 0141 环形链表
• 0142 环形链表 II
• 0160 相交链表
• 0876 链表的中间结点

2.3 排序

• 0021 合并两个有序链表
• 0023 合并K个升序链表
• 0147 对链表进行插入排序
• 0148 排序链表

3 挑战

3.1 设计

• 0138 复制带随机指针的链表
• 0430 扁平化多级双向链表
• 0432 全 O(1) 的数据结构
• 1206 设计跳表

3.2 操作

• 0206 反转链表
• 0092 反转链表 II
• 0025 K 个一组翻转链表
• 0143 重排链表
• 0234 回文链表