linked-list
文档摘要
确保翻译不显得太生硬。确保翻译注释。 这个文件是用Markdown格式写的。不要把它当作XML或HTML。 不要翻译任何[!NOTE]、[!WARNING]、[!TIP]、[!IMPORTANT]或[!CAUTION]。 不要翻译任何实体，如变量名、函数名、类名，或占位符如@@INLINECODEx@@或@@CODEBLOCKx@@，但保留它们在文件中。 不要翻译任何URL或路径，但保留它们在文件中。 请从左到右写输出。
确保翻译不显得太生硬。确保翻译注释。
这个文件是用Markdown格式写的。不要把它当作XML或HTML。
不要翻译任何[!NOTE]、[!WARNING]、[!TIP]、[!IMPORTANT]或[!CAUTION]。
不要翻译任何实体，如变量名、函数名、类名，或占位符如@@INLINE_CODE_x@@或@@CODE_BLOCK_x@@，但保留它们在文件中。
不要翻译任何URL或路径，但保留它们在文件中。
请从左到右写输出。
id: 链表
title: 编码面试链表速查表
description: 编码面试链表学习指南，包括练习题、技巧、时间复杂度和推荐资源
keywords:
[
链表编码面试学习指南,
链表编码面试技巧,
链表练习题,
链表实用技巧,
链表时间复杂度,
链表推荐学习资源,
]
sidebar_label: 链表
toc_max_heading_level: 2
引言
与数组类似，链表用于表示顺序数据。它是一种线性数据集合，其元素的顺序并非由它们在内存中的物理位置决定，这与数组不同——数组的数据存储在连续的内存块中。相反，每个元素都包含指向下一个元素的地址。链表是一种由节点组成的结构，这些节点共同代表一个序列。
在最基本的形式中，每个节点包含：数据，以及对序列中下一个节点的引用（换句话说，就是链接）。
优点
在链表中，给定节点的位置后，插入和删除节点的时间复杂度为O(1)，而在数组中，后续元素则需要移动。
缺点
访问时间是线性的，因为无法直接通过链表中的位置访问元素（在数组中可以这样做，例如arr[4]）。你必须从头开始遍历。
学习资源
- 阅读材料
- 链表到底是什么？[第一部分], basecs
- 链表到底是什么？[第二部分], basecs
- 视频
链表的类型
单向链表
一种链表，其中每个节点指向下一个节点，最后一个节点指向null。
双向链表
一种链表，其中每个节点有两个指针，next指向下一个节点，prev指向前一个节点。第一个节点的prev指针和最后一个节点的next指针都指向null。
循环链表
一种单向链表，其中最后一个节点指向第一个节点。还有一种循环双向链表变体，其中第一个节点的prev指针指向最后一个节点，最后一个节点的next指针指向第一个节点。
实现方式
在常见的编程语言中，只有Java提供了链表的实现。不过，无论使用哪种语言，自己编写链表都非常简单。
| 语言 | API |
|---|---|
| C++ | std::list |
| Java | java.util.LinkedList |
| Python | 无 |
| JavaScript | 无 |
时间复杂度
| 操作 | 大O | 注释 |
|---|---|---|
| 访问 | O(n) | |
| 查找 | O(n) | |
| 插入 | O(1) | 假设你已经遍历到插入位置 |
| 删除 | O(1) | 假设你已经遍历到要删除的节点 |
常见操作
熟悉以下操作，因为许多链表问题的解法都会用到这些操作之一或多个：
- 统计链表中节点的数量
- 在原地反转链表
- 使用快慢指针找到链表的中间节点（快慢指针）
- 合并两个链表
边界情况
- 空链表（头为
null） - 单个节点
- 两个节点
- 链表存在环。提示： 提前与面试官确认链表是否允许存在环。通常答案是不允许，因此你无需在代码中处理环的情况
技巧
哨兵/虚拟节点
在链表的头和/或尾部添加一个哨兵/虚拟节点，有助于处理很多边界情况，比如需要在头或尾部进行操作时。虚拟节点的存在本质上保证了操作永远不会发生在头或尾部，从而省去了大量处理空指针的条件判断。记得在操作结束时将它们移除。
快慢指针
快慢指针方法在链表中也很常见。这种方法被用于许多经典的链表问题。
- 获取倒数第k个节点——设置两个指针，其中一个比另一个提前k个节点。当快指针到达末尾时，慢指针就位于倒数第k个节点
- 检测环——设置两个指针，其中一个指针的步长是另一个的两倍。如果两个指针相遇，则说明链表存在环
- 获取中间节点——设置两个指针，其中一个指针的步长是另一个的两倍。当快指针到达链表末尾时，慢指针就位于中间
利用额外空间
许多链表问题可以通过创建一个新的链表，并将结果节点添加到新链表中来轻松解决。然而，这会占用额外的空间，使问题的挑战性降低。面试官通常会要求你在原地修改链表，而无需额外存储。你可以借鉴【反转链表】（https://leetcode.com/problems/reverse-linked-list/）问题的思路。
精妙的修改操作
如前所述，链表的非连续内存特性使其内容的修改非常高效。与数组只能修改某个位置的值不同，链表除了可以修改value，还可以修改next指针。
以下是一些常见的操作及其简便实现方法：
- 截断链表——将最后一个元素的
next指针设置为null - 交换节点的值——与数组一样，只需交换两个节点的值，无需交换
next指针 - 合并两个链表——将第二个链表的头连接到第一个链表的尾部
必备题目
如果你正在备考这个主题，这些题目是必练的。
- 【反转链表】（https://leetcode.com/problems/reverse-linked-list/）
- 【检测链表中是否存在环】（https://leetcode.com/problems/linked-list-cycle/）
推荐练习题目
在你学完这个主题并练习过必备题目之后，建议做这些题目。
- 【合并两个有序链表】（https://leetcode.com/problems/merge-two-sorted-lists/）
- 【合并K个有序链表】（https://leetcode.com/problems/merge-k-sorted-lists/）
- 【删除链表倒数第N个节点】（https://leetcode.com/problems/remove-nth-node-from-end-of-list/）
- 【重新排列链表】（https://leetcode.com/problems/reorder-list/）
推荐课程
import AlgorithmCourses from '../_courses/AlgorithmCourses.md'
免责声明：
本文档采用基于机器的 AI 翻译服务进行翻译。尽管我们力求准确，但请注意，自动翻译可能存在错误或不准确之处。应以原文语言版本的文档作为权威依据。如需获取关键信息，建议使用专业的人工翻译。对于因使用本翻译而产生的任何误解或误读，我们概不负责。