Algorithms study cheatsheets
Coding interview 的 Linked List cheatsheet
Linked List 学习指南，包含练习题、技巧、时间复杂度与推荐资源
Introduction
和 array 一样，linked list 用于表示序列数据。不同的是，linked list 的顺序不由内存中物理位置决定，而是通过节点的指针相连。每个 node 包含 data 和 next 指针（指向下一个 node）。
Advantages
在已知位置时，插入/删除节点是 O(1)，而数组需要移动后续元素。
Disadvantages
随机访问慢。无法像数组那样 arr[4] 直接取值，必须从头遍历，因此是 O(n)。
Learning resources
- Readings
- Videos
- Singly-linked lists, University of California San Diego
- Doubly linked lists, University of California San Diego
Types of linked lists
Singly linked list
每个 node 指向下一个 node，最后一个 node 的 next 指向 null。
Doubly linked list
每个 node 有 next 和 prev 指针。第一个 node 的 prev 和最后一个 node 的 next 指向 null。
Circular linked list
单向链表中最后一个 node 指回第一个 node。还有 circular doubly linked list：第一个 node 的 prev 指向最后一个 node，最后一个 node 的 next 指向第一个 node。
Implementations
常见语言里只有 Java 提供 linked list 实现。自己实现也不难。
| Language | API |
|---|---|
| C++ | std::list |
| Java | java.util.LinkedList |
| Python | N/A |
| JavaScript | N/A |
Time complexity
| Operation | Big-O | Note |
|---|---|---|
| Access | O(n) | |
| Search | O(n) | |
| Insert | O(1) | 前提是你已遍历到插入位置 |
| Remove | O(1) | 前提是你已遍历到要删除节点 |
Common routines
linked list 题常见套路：
- 统计节点数量
- in-place 反转链表
- 用 fast/slow 指针找中间节点
- 合并两个链表
Corner cases
- 空链表（head 为
null） - 单节点
- 两节点
- 链表有环。Tip: 提前问面试官是否可能有环，通常没有，不用处理。
Techniques
Sentinel/dummy nodes
在 head/tail 加 dummy node 可处理很多边界情况，避免对 head/tail 做复杂判断。记得操作结束后移除 dummy。
Two pointers
双指针是经典套路：
- 找倒数第 k 个节点：一个指针领先 k 个节点，领先指针到尾时，另一个即倒数第 k
- 检测环：一快一慢指针，若相遇则有环
- 找中间节点：快指针是慢指针的两倍速度，快到尾时慢在中间
Using space
很多题可以新建链表解决，但会用额外空间，难度变低。面试官通常要求 in-place 修改。可以参考 Reverse a Linked List 的思路。
Elegant modification operations
Linked list 可修改 next 指针，操作灵活：
- Truncate list - 最后一个 node 的
next设为null - Swapping values - 直接交换 value，无需动
next - Combining lists - 把第二个 list 的 head 接到第一个 list 的 tail
Essential questions
该 topic 必练题。
Recommended practice questions
在掌握基础后推荐练习。