链表的套路都在这里了

链表介绍

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

在最基本的单向链表中，每个节点包含：数据和指向下一个节点的next指针。

链表的优点

在链中插入和删除节点（给定其位置时）的时间复杂度为 O(1)，而在数组中插入和删除的平均时间复杂度为 O(n)，因为必须对插入或删除位置后面的元素进行移动。

链表的缺点

对链表中的元素访问时间是线性的，即 O(n)，因为直接通过链表中的位置访问元素是不可能的，不像数组可以直接通过给定的索引访问指定元素，比如可以通过arr[4]直接访问数组arr的第4个元素。但是链表必须从头开始遍历。

常见链表的类型

单向链表

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

双向链表

双向链表的每个节点有两个指针，next 指向下一个节点，prev 指向前一个节点。第一个节点的prev指针和最后一个节点的next指针都指向空节点。

循环链表

对于循环单向链表，它的最后一个节点指向第一个节点。

对于循环双向链表，它的第一个节点的 prev 指针指向最后一个节点，最后一个节点的 next 指针指向第一个节点。

链表操作的时间复杂度

操作	平均时间复杂度	备注
访问	O(n)
查找	O(n)
插入	O(1)	已经遍历到插入位置的前提下
删除	O(1)	已经遍历到删除位置的前提下

链表常见操作

对于链表学习，需要熟练掌握下面的一些操作，因为很对面试题都是基于下面的操改造的。

• 计算链表中元素的个数。
• 原地反转一个链表，即需要空间复杂度为 O(1)。
• 利用快慢指针寻找链表中间的元素。
• 合并两个有序链表为一个有序链表。

链表常见的边界条件

• 空链表
• 只有一个节点的链表
• 只有两个节点的链表
• 带有环的链表

处理链表问题常用的方法

1. 添加一个哨兵节点（也叫虚拟节点）

在头部或尾部添加哨兵节点可以避免处理在头部或尾部的一些边界情况。哨兵节点本质上确保了永远不会在头部或尾部进行操作，从而避免了编写额外的逻辑处理空指针的麻烦。操作结束时一定要记住将哨兵节点删除。

2. 双指针

很多经典的链表问题都是使用双指针来解的。

• 获取单向链表倒数第 k 个节点，定义两个指针，其中一个指针比另一个指针领先 k 个节点。当前面的节点到达末尾时，另一个节点就是倒数第 k 个节点。

• 检测链表中是否存在环，定义两个指针，其中一个指针移动的步长是另一个指针移动步长的两倍，如果两个指针相遇，则意味着存在环。有些时候面试官还进一步让你找到环的入口节点，这个时候只需要在两个指针相遇的时候，让快指针也慢下来，移动步长改为和慢指针的步长一致，慢指针挪到链表头节点开始移动，直到他俩再次相遇，此时的节点就是环的入口。

• 获取单向链表的中间节点，定义两个指针，其中一个指针移动的步长是另一个指针移动步长的两倍。当较快的指针到达链表末尾时，较慢的指针就位于链表的中间节点。

• 寻找两个相交单链表的交汇点，定义两个指针，分别从两个链表的头节点开始遍历，遍历到null节点，继续从对方头节点开始遍历，直到两个指针相遇，相遇的节点就是两个单链表的交汇点。

3. 是否使用额外空间

许多链表问题可以通过创建一个新的链表并将节点添加到新的链表中并得到最终结果来轻松解决。然而，这会占用额外的空间，并使问题变得不那么具有挑战性。面试官通常会要求你就地修改链表并解决问题，无需额外空间。你可以借用“反转链表”问题的思路。

4. 一些高效的操作

链表的内存非连续性使得对链表节点的修改特别高效。与只能修改某个位置的值的数组不同，链表不但可以修改某个节点的值，还可以修改其next指针的指向。

以下是一些常见操作：

• 链表的截断，将最后一个元素的next指针设置为 null 。
• 交换节点的值，就像数组一样，只需交换两个节点的值即可，无需交换next指针。
• 合并两个单向链表，将第一个列表的尾部指向第二个列表的头部。