算法总结 | 技术面试手册 | tech-interview-handbook 中文文档

id: 链表标题：编码面试中链表的速查手册描述：编码面试中链表的学习指南，包括实践问题、技巧、时间复杂度以及推荐资源关键词： [ 链表编码面试学习指南，链表编码面试技巧，链表实践问题，链表有用技巧，链表时间复杂度，链表推荐学习资源 ] 侧边栏标签：链表目录最大标题级别：2

引言

与数组一样，链表用于表示顺序数据。它是数据元素的线性集合，其顺序不是由内存中物理位置决定的，而数组则是按照连续的内存块存储数据的。相反，每个元素都包含一个指向下一个元素的地址。它是由一组节点组成的集合，这些节点共同表示一个序列。

在最基本的形式中，每个节点包含：数据和指向序列中下一个节点的引用（换句话说，链接）。

优点

在列表中的某个位置插入和删除节点（假设其位置已知）是O(1)的，而在数组中需要移动以下元素。

缺点

访问时间是线性的，因为不能直接通过列表中的位置访问元素（在数组中你可以执行arr[4]）。你必须从头开始遍历。

学习资源

阅读材料
到底什么是链表？[第一部分]，basecs
到底什么是链表？[第二部分]，basecs
视频
单链表，加州大学圣地亚哥分校
双链表，加州大学圣地亚哥分校

链表类型

单向链表

每个节点指向下一个节点，最后一个节点指向null的单向链表。

双向链表

每个节点有两个指针，next指向下一个节点，prev指向前一个节点。第一个节点的prev指针和最后一个节点的next指针指向null。

循环链表

单向链表，最后一个节点指向第一个节点。有一种循环双向链表变体，其中第一个节点的prev指针指向最后一个节点，最后一个节点的next指针指向第一个节点。

实现

在常见语言中，只有Java提供了链表实现。幸运的是，无论使用哪种语言，编写自己的链表都是非常容易的。

语言	API
C++	N/A
Java	`java.util.LinkedList`
Python	N/A
JavaScript	N/A

时间复杂度

操作	大O表示法	注意事项
访问	O(n)
搜索	O(n)
插入	O(1)	假设你已经遍历到插入位置
删除	O(1)	假设你已经遍历到要删除的节点

常见程序

熟悉以下程序，因为许多链表问题在解决方案中会使用这些程序中的一个或多个：

计算链表中的节点数量
在原地反转链表
使用两个指针找到链表的中点（快/慢）
合并两个链表

特殊情况

空链表（头是null）
单节点
两个节点
链表有循环。提示：事先与面试官澄清列表中是否可能有循环。通常答案是没有，并且你不需要在代码中处理这种情况

技巧

虚拟节点/哨兵节点

在头部和/或尾部添加虚拟节点可以帮助处理许多需要在头部或尾部执行操作的边缘情况。虚拟节点的存在本质上确保了操作永远不会在头部或尾部进行，从而消除了编写条件检查和处理空指针的大量头痛。请确保在操作结束时删除它们。

双指针

对于链表，双指针方法也很常见。这种方法用于许多经典的链表问题。

获取倒数第k个节点 - 有两个指针，一个在另一个前面k个节点。当前面的节点到达末尾时，另一个节点在前面k个节点后面
检测循环 - 有两个指针，一个指针比另一个多递增两倍，如果两个指针相遇，意味着有循环
获取中间节点 - 有两个指针，一个指针比另一个多递增两倍。当快速节点到达列表末尾时，较慢的节点将在中间

空间利用

许多链表问题可以通过创建一个新的链表并将最终结果添加到新链表中来轻松解决。然而，这会占用额外的空间，使问题变得更具挑战性。面试官通常会要求你在原地修改链表，并在不使用额外存储的情况下解决问题。你可以从反转链表问题中借用工具。

优雅的修改操作

如前所述，链表的非顺序内存特性允许高效地修改其内容。与数组不同，在数组中你只能修改特定位置的值，而对于链表，你还可以修改next指针而不是value。以下是一些常见的操作及其如何轻松实现的方法：

截断列表 - 在最后一个元素处将 next 指针设置为 null
交换节点的值 - 就像数组一样，只需交换两个节点的值即可，无需交换 next 指针
合并两个列表 - 将第二个列表的头部附加到第一个列表的尾部

基本问题

如果你正在为这个主题学习，练习这些基本问题是必要的。

引言