编码面试的链接列表备忘单
原文：https://www.techinterviewhandbook.org/algorithms/linked-list/
简介
像数组一样，链表也用来表示顺序数据。它是数据元素的线性集合，其顺序不是由它们在内存中的物理位置给出的，这与数组相反，数组中的数据存储在顺序的内存块中。相反，每个元素包含下一个元素的地址。它是一种数据结构，由共同代表一个序列的节点集合组成。
在最基本的形式中，每个节点包含:数据，以及对序列中下一个节点的引用(换句话说，链接)。
优势
在列表中插入和删除一个节点(给定它的位置)是 O(1)，而在数组中，下面的元素必须移位。
缺点
访问时间是线性的，因为通过元素在列表中的位置直接访问元素是不可能的(例如，在数组中你可以做arr[4])。你必须从头开始穿越。
学习资源
链表的类型
单链表
一个链表，其中每个节点指向下一个节点，最后一个节点指向null。
双向链表
一个链表，其中每个节点有两个指针，next指向下一个节点，prev指向前一个节点。第一个节点的prev指针和最后一个节点的next指针指向null。
循环链表
一个单链表，其中最后一个节点指向第一个节点。有一种循环双向链表变体，其中第一个节点的prev指针指向最后一个节点，最后一个节点的next指针指向第一个节点。
实现
在通用语言中，只有 Java 提供了链表实现。谢天谢地，不管用什么语言，编写自己的链表都很容易。
| 语言 | 应用程序接口 |
|---|---|
| C++ | 不适用的 |
| Java 语言(一种计算机语言，尤用于创建网站) | T2java.util.LinkedList |
| 计算机编程语言 | 不适用的 |
| Java Script 语言 | 不适用的 |
时间复杂度
| 操作 | 大 O | 注意 |
|---|---|---|
| 接近 | O(n) | |
| 搜索 | O(n) | |
| 插入 | O(1) | 假设您已经遍历到插入位置 |
| 去除 | O(1) | 假设您已经遍历到要删除的节点 |
常用套路
熟悉以下例程，因为许多链表问题在解决方案中使用了一个或多个这些例程:
- 计算链表中的节点数
- 就地反转链接列表
- 使用两个指针(快/慢)查找链表的中间节点
- 将两个链表合并在一起
拐角情况
- 空链表(表头为
null) - 单一节点
- 两个音符
- 链表有循环。提示:事先和面试官明确，列表中是否可以有循环。通常答案是否定的，你不必在代码中处理它
技巧
前哨/伪节点
在头部和/或尾部添加前哨/伪节点可能有助于处理必须在头部或尾部执行操作的许多边缘情况。虚拟节点的存在实质上确保了操作永远不会在头部或尾部完成，从而消除了编写条件检查来处理空指针时的许多麻烦。请务必记住在操作结束时将它们移除。
两个指针
对于链表，两种指针方法也很常见。这种方法用于许多经典的链表问题。
- 从最后一个节点获取第 k 个节点——有两个指针，其中一个比另一个领先 k 个节点。当前面的节点到达终点时，另一个节点落后 k 个节点
- 检测周期——有两个指针，其中一个指针的增量是另一个指针的两倍，如果两个指针相遇，就意味着有周期
- 获取中间节点——有两个指针，其中一个指针的增量是另一个的两倍。当速度较快的节点到达列表末尾时，速度较慢的节点将位于中间
使用空格
许多链表问题可以通过创建一个新的链表并向新的链表添加节点以及最终结果来轻松解决。然而，这占用了额外的空间，使得问题的挑战性大大降低。面试官通常会要求你就地修改链表，在没有额外存储的情况下解决问题。你可以借用逆向链表问题的思路。
优雅的修改操作
如前所述，链表的非顺序内存特性允许有效地修改其内容。与只能修改某个位置的值的数组不同，对于链表，除了修改value之外，还可以修改next指针。
以下是一些常见操作以及如何轻松实现这些操作:
- 截断一个列表——将
next指针设置为指向最后一个元素的null - 交换节点的值——就像数组一样，只交换两个节点的值，不需要交换
next指针 - 合并两个列表——将第二个列表的头部附加到第一个列表的尾部
基本问题
如果你在学习这个话题，这些是需要练习的基本问题。
推荐练习题
这些是在你为题目学习并练习了基本问题后推荐练习的问题。
推荐课程
AlgoMonsterT3】
AlgoMonster 旨在帮助你在最短的时间内通过技术面试。由谷歌工程师开发的 AlgoMonster 使用数据驱动的方法来教你最有用的关键问题模式，并有内容帮助你快速修改基本的数据结构和算法。最重要的是，AlgoMonster 不是基于订阅的——支付一次性费用，就可以获得终身访问。 今天加入七折优惠→
寻找编码面试:编码问题的模式
设计大师的这门课程扩展了推荐练习题中的问题，但从问题模式的角度来进行练习，这是一种我也同意的学习方法，我个人也使用这种方法来更好地编写面试代码。本课程允许你用 Java、Python、C++、JavaScript 来练习选定的问题，并提供这些语言的示例解决方案以及一步一步的可视化。学习和理解模式，而不是背答案！ 现在获得终身使用权→
掌握编码面试:数据结构+算法
这本 Udemy 畅销书是评分最高的面试准备课程之一(4.6 星，21.5k 评分，135k 学生)，包含了价值 19 个小时的内容。像技术面试手册一样，它超越了编码面试，涵盖了简历，非技术面试，谈判。是一个全包！请注意，JavaScript 用于编码演示。 结账→
