链表
与数组相似，链表也是一种
线性
数据结构。这里有一个例子：
链表中的每个元素实际上是一个单独的对象，而所有对象都通过每个元素中的引用字段链接在一起。
链表有两种类型：单链表和双链表。上面给出的例子是一个单链表，这里有一个双链表的例子：
一 简介 - 单链表
单链表中的每个结点不仅包含
值
，还包含链接到下一个结点的
引用字段
。通过这种方式，单链表将所有结点按顺序组织起来。
1. 结点结构
在大多数情况下，我们将使用头结点(第一个结点)来表示整个列表。
// Definition for singly-linked list.
struct SinglyListNode {
int val;
SinglyListNode *next;
SinglyListNode(int x) : val(x), next(NULL) {}
};
2. 操作
与数组不同，我们无法在常量时间内访问单链表中的随机元素。 如果我们想要获得第 i 个元素，我们必须从头结点逐个遍历。 我们按
索引
来
访问元素
平均要花费
O(N)
时间，其中 N 是链表的长度。
例如，在上面的示例中，头结点是 23。访问第 3 个结点的唯一方法是使用头结点中的“next”字段到达第 2 个结点（结点 6）; 然后使用结点 6 的“next”字段，我们能够访问第 3 个结点。
你可能想知道为什么链表很有用，尽管它在通过索引访问数据时（与数组相比）具有如此糟糕的性能。 接下来，我们将介绍插入和删除操作，你将了解到链表的好处。
2.1 添加操作 - 单链表
如果我们想在给定的结点
prev
之后添加新值，我们应该：
- 使用给定值初始化新结点
cur；
单链表和双链表 - 将
cur
next
单链表和双链表 - 将
prev
cur
单链表和双链表
与数组不同，我们不需要将所有元素移动到插入元素之后。因此，您可以在
O(1)
时间复杂度中将新结点插入到链表中，这非常高效。
示例
让我们在第二个结点 6 之后插入一个新的值 9。
我们将首先初始化一个值为 9 的新结点。然后将结点 9 链接到结点 15。最后，将结点 6 链接到结点 9。
插入之后，我们的链表将如下所示：
2.2 在开头添加结点
众所周知，我们使用头结点来代表整个列表。
因此，在列表开头添加新节点时更新头结点
head
至关重要。
- 初始化一个新结点
cur；
- 将新结点链接到我们的原始头结点
head
- 将
cur
head
例如，让我们在列表的开头添加一个新结点 9。
- 我们初始化一个新结点 9 并将其链接到当前头结点 23。
单链表和双链表 - 指定结点 9 为新的头结点。
单链表和双链表
2.3 删除操作 - 单链表
如果我们想从单链表中删除现有结点
cur
，可以分两步完成：
- 找到 cur 的上一个结点
prev
next；
单链表和双链表 - 接下来链接
prev
next。
单链表和双链表
在我们的第一步中，我们需要找出
prev
和
next
。使用
cur
的参考字段很容易找出
next
，但是，我们必须从头结点遍历链表，以找出
prev
，它的平均时间是
O(N)
，其中 N 是链表的长度。因此，删除结点的时间复杂度将是
O(N)
。
空间复杂度为
O(1)
，因为我们只需要常量空间来存储指针。
示例
让我们尝试把结点 6 从上面的单链表中删除。
- 从头遍历链表，直到我们找到前一个结点
prev
- 将
prev
next
结点 6 现在不在我们的单链表中。
2.4 删除第一个结点
如果我们想删除第一个结点，策略会有所不同。
正如之前所提到的，我们使用头结点
head
来表示链表。我们的头是下面示例中的黑色结点 23。
如果想要删除第一个结点，可以简单地
将下一个结点分配给 head
。也就是说，删除之后我们的头将会是结点 6。
链表从头结点开始，因此结点 23 不再在我们的链表中。
3. 链表中的双指针
让我们从一个经典问题开始：
给定一个链表，判断链表中是否有环。
你可能已经使用
哈希表
提出了解决方案。但是，使用
双指针技巧
有一个更有效的解决方案。
想象一下，有两个速度不同的跑步者。如果他们在直路上行驶，快跑者将首先到达目的地。但是，如果它们在圆形跑道上跑步，那么快跑者如果继续跑步就会追上慢跑者。
这正是我们在链表中使用两个速度不同的指针时会遇到的情况：
-
如果没有环，快指针将停在链表的末尾。
-
如果有环，快指针最终将与慢指针相遇。
所以剩下的问题是：
这两个指针的适当速度应该是多少？
一个安全的选择是每次移动慢指针
一步
，而移动快指针
两步
。每一次迭代，快速指针将额外移动一步。如果环的长度为 M，经过 M 次迭代后，快指针肯定会多绕环一周，并赶上慢指针。
那其他选择呢？它们有用吗？它们会更高效吗？
// Initialize slow & fast pointers
ListNode* slow = head;
ListNode* fast = head;
/**
* Change this condition to fit specific problem.
* Attention: remember to avoid null-pointer error
**/
while (slow && fast && fast->next) {
slow = slow->next; // move slow pointer one step each time
fast = fast->next->next; // move fast pointer two steps each time
if (slow == fast) { // change this condition to fit specific problem
return true;
}
}
return false; // change return value to fit specific problem
提示
它与我们在数组中学到的内容类似。但它可能更棘手而且更容易出错。你应该注意以下几点：
1. 在调用 next 字段之前，始终检查节点是否为空。
获取空节点的下一个节点将导致空指针错误。例如，在我们运行
fast = fast.next.next
之前，需要检查
fast
和
fast.next
不为空。
2. 仔细定义循环的结束条件。
运行几个示例，以确保你的结束条件不会导致无限循环。在定义结束条件时，你必须考虑我们的第一点提示。
复杂度分析
空间复杂度分析容易。如果只使用指针，而不使用任何其他额外的空间，那么空间复杂度将是
O(1)
。但是，时间复杂度的分析比较困难。为了得到答案，我们需要分析
运行循环的次数
。
在前面的查找循环示例中，假设我们每次移动较快的指针 2 步，每次移动较慢的指针 1 步。
- 如果没有循环，快指针需要
N/2 次
- 如果存在循环，则快指针需要
M 次
显然，M <= N 。所以我们将循环运行
N
次。对于每次循环，我们只需要常量级的时间。因此，该算法的时间复杂度总共为
O(N)
。
自己分析其他问题以提高分析能力。别忘了考虑不同的条件。如果很难对所有情况进行分析，考虑最糟糕的情况。
4. 反转链表
让我们从一个经典问题开始：
反转一个单链表。
一种解决方案是
按原始顺序迭代结点
，并将它们
逐个移动到列表的头部
。似乎很难理解。我们先用一个例子来说明我们的算法。
算法概述
让我们看一个例子：
请记住，黑色结点 23 是原始的头结点。
- 首先，我们将黑色结点的下一个结点（即结点 6）移动到列表的头部：
- 然后，我们将黑色结点的下一个结点（即结点 15）移动到列表的头部：
- 黑色结点的下一个结点现在是空。因此，我们停止这一过程并返回新的头结点 15。
更多
在该算法中，每个结点
只移动一次
。
因此，时间复杂度为
O(N)
，其中 N 是链表的长度。我们只使用常量级的额外空间，所以空间复杂度为
O(1)。
二 简介 - 双链表
单链接列表中的结点具有 Value 字段，以及用于顺序链接结点的“Next”引用字段。
在本文中，我们将介绍另一种类型的链表：
双链表
。
1. 定义
双链表以类似的方式工作，但
还有一个引用字段
，称为
“prev”
字段。有了这个额外的字段，您就能够知道当前结点的前一个结点。
让我们看一个例子：
绿色箭头表示我们的“prev”字段是如何工作的。
2. 结点结构
下面是双链表中结点结构的典型定义：
// Definition for doubly-linked list.
struct DoublyListNode {
int val;
DoublyListNode *next, *prev;
DoublyListNode(int x) : val(x), next(NULL), prev(NULL) {}
};
与单链接列表类似，我们将使用
头结点
来表示整个列表。
3. 操作
与单链表类似，我们将介绍在双链表中如何访问数据、插入新结点或删除现有结点。
我们可以与单链表相同的方式访问数据：
- 我们不能在常量级的时间内
访问随机位置
- 我们必须从头部遍历才能得到我们想要的第一个结点。
- 在最坏的情况下，时间复杂度将是
O(N)
N
对于添加和删除，会稍微复杂一些，因为我们还需要处理“prev”字段。
3.1 添加操作 - 双链表
如果我们想在现有的结点
prev
之后插入一个新的结点
cur
，我们可以将此过程分为两个步骤：
- 链接
cur
prev
next
next
prev
单链表和双链表 - 用
cur
prev
next
单链表和双链表
与单链表类似，添加操作的时间和空间复杂度都是
O(1)
。
示例
让我们在现有结点 6 之后添加一个新结点 9：
- 链接
cur
prev
next
单链表和双链表 - 用
cur
prev
next
单链表和双链表
3.2 删除操作 - 双链表
如果我们想从双链表中删除一个现有的结点
cur
，我们可以简单地将它的前一个结点
prev
与下一个结点
next
链接起来。
与单链表不同，使用“prev”字段可以很容易地在常量时间内获得前一个结点。
因为我们不再需要遍历链表来获取前一个结点，所以时间和空间复杂度都是
O(1)
。
示例
我们的目标是从双链表中删除结点 6。
因此，我们将它的前一个结点 23 和下一个结点 15 链接起来：
结点 6 现在不在我们的双链表中。
三 小结 - 链表
让我们简要回顾一下单链表和双链表的表现。
它们在许多操作中是相似的。
- 它们都无法在常量时间内
随机访问数据
- 它们都能够
在 O(1) 时间内在给定结点之后或列表开头添加一个新结点
- 它们都能够
在 O(1) 时间内删除第一个结点
但是删除给定结点(包括最后一个结点)时略有不同。
- 在单链表中，它无法获取给定结点的前一个结点，因此在删除给定结点之前我们必须花费
O(N)
- 在双链表中，这会更容易，因为我们可以使用“prev”引用字段获取前一个结点。因此我们可以在
O(1)
对照
这里我们提供链表和其他数据结构（包括数组，队列和栈）之间
时间复杂度
的比较：
经过这次比较，我们不难得出结论：
如果你需要经常添加或删除结点，链表可能是一个不错的选择。
如果你需要经常按索引访问元素，数组可能是比链表更好的选择。