链表

目的与范围

本文档全面概述了LeetCode-Master仓库中涉及的链表知识。链表是基本的数据结构，可作为基于指针的数据结构和内存管理的入门。在该仓库的学习路径中，链表排在数组之后、哈希表之前，代表着从连续内存结构到基于节点的数据结构的逻辑演进。

本文档涵盖了链表的实现、常见操作、问题解决模式以及演示链表操作技巧的关键LeetCode问题。

来源： README.md114-124

链表基础

链表是一种线性数据结构，由节点组成，每个节点包含数据以及指向序列中下一个节点的引用（或指针）。与数组不同，链表不需要连续的内存分配，并且可以在程序执行期间动态增长或缩小。

来源： problems/链表理论基础.md

链表的类型

来源： problems/链表理论基础.md

节点结构

在该仓库中，链表节点通常使用以下结构实现

这个定义在该仓库的所有链表问题中都保持一致。

来源： problems/0203.移除链表元素.md problems/0707.设计链表.md

常用操作

遍历

遍历链表涉及从头到尾依次访问每个节点。

插入

插入节点需要调整现有节点的指针。

删除

删除节点涉及在链表结构中绕过它。

来源： problems/链表理论基础.md problems/0707.设计链表.md

关键问题解决模式

双指针技术

双指针技巧是许多链表算法的基础

来源： problems/0142.环形链表II.md problems/0019.删除链表的倒数第N个节点.md

虚拟头节点模式

虚拟头节点技巧简化了可能影响头节点的操作

这种模式避免了在头节点可能改变时进行特殊情况处理的需要。

来源： problems/0203.移除链表元素.md problems/0024.两两交换链表中的节点.md

关键LeetCode问题

该仓库涵盖了这些重要的链表问题

问题	描述	关键技术
203. 移除链表元素	移除所有具有特定值的元素	虚拟头节点
707. 设计链表	实现带操作的链表	核心操作的实现
206. 翻转链表	翻转单向链表	迭代/递归指针操作
24. 两两交换链表中的节点	每两个相邻节点进行交换	虚拟头节点，仔细的指针操作
19. 删除链表的倒数第N个节点	移除倒数第N个节点	快慢指针带偏移量
两个链表的交点	查找两个链表相交的节点	双指针对齐技巧
142. 环形链表II	查找环的入口	弗洛伊德判圈算法

来源： README.md114-124

高级技巧

使用弗洛伊德算法检测环

弗洛伊德判圈算法（又称“龟兔赛跑算法”）

来源： problems/0142.环形链表II.md

反转链表

来源： problems/0206.翻转链表.md

实现考量

常见陷阱

使用链表时，请注意以下常见问题

空指针解引用
丢失头节点引用
未正确处理边界情况（空链表、单节点）
节点计数时的一位偏差错误
手动内存管理语言中的内存泄漏

性能特征

操作	时间复杂度	备注
访问	O(n)	无随机访问能力
在开头插入	O(1)	只需更新头指针
在末尾插入	O(n) 或 O(1)	如果维护尾指针则为 O(1)
在中间插入	O(n)	需要遍历到插入点
在开头删除	O(1)	只需更新头指针
在末尾删除	O(n)	需要找到倒数第二个节点
在中间删除	O(n)	需要遍历到删除点
搜索	O(n)	需要顺序查找

来源： problems/链表总结篇.md

时空权衡

维护尾指针：允许在末尾进行O(1)插入，但需要额外的内存
虚拟头节点：通过消除边界情况来简化代码，但会占用额外内存
递归 vs. 迭代：递归解决方案通常更简洁，但会占用O(n)的栈空间