一、链表概念链表属于线性表逻辑上元素是连续序列但物理内存不一定连续。 链表由一个个结点组成每个结点分为两部分数据域存储有效数据指针域存储下一个结点的地址依靠指针把结点串接起来结点从堆上动态malloc申请两次申请的内存地址可以连续也可以不连续由操作系统分配。通俗理解顺序表相当于电影院连续连号座位链表相当于人分散各处每个人保存下一个人的位置信息。二、链表的8种组合分类三组特征自由组合一共8种链表单向 / 双向带头结点 / 不带头结点循环 / 非循环笔试、工程实际只重点掌握2种1. 无头单向非循环链表笔试OJ高频typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;只能向后遍历无法回退无哨兵头结点。应用很少单独存储业务数据多用于哈希桶、图邻接表大量出现在笔试题。坑点头插、头删会改变链表头指针函数需要传二级指针。2. 带头双向循环链表工程实际常用typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* next; struct ListNode* prev; }ListNode;存在哨兵头结点不存有效数据尾结点next指向头头结点prev指向尾。结构看着复杂但编码简单空链表、头结点、尾结点不需要特殊边界处理。总结考试刷题重点考无头单向非循环链表实际开发优先带头双向循环链表。三、单链表基础接口考点基础接口BuySListNode申请结点、打印、头插、尾插、头删、尾删、查找、SListInsertAfter、SListEraseAfter。考点为什么单链表多用pos之后插入/删除很少在pos之前操作 单链表没有前驱指针在pos前面插入需要从头遍历找pos的前一个结点时间复杂度O(N)在pos后面插入删除直接修改指针O(1)即可完成。四、链表经典OJ考点删除链表中等于val的所有结点反转单链表求链表中间结点快慢指针slow走1步fast走2步fast到末尾slow即为中间结点求链表倒数第k个结点合并两个有序链表按照x分割链表判断链表回文结构求两个链表第一个相交结点注意相交判断看结点地址是否相等不是看存储的数据值一旦相交后续结点全部共用。1. 判断链表是否有环 LeetCode141快慢指针slow一次走1步fast一次走2步都从head出发。有环快慢指针一定会在环内相遇无环fast走到NULL结束。面试问答为什么fast走2步、slow走1步一定能追上fast走3步行不行 环内相对速度为1每次两者距离减1最终必定相遇。 如果fast走3步相对速度为2若环内初始间隔是奇数会直接跨过慢指针永远无法相遇。2. 寻找入环的第一个结点 LeetCode142⚠️重要快慢指针相遇点不等于环入口。公式推导 L起点H到环入口E距离X入口E到相遇点M距离R环的总长度 slow路程$(LX)$ fast路程$2((LX))(LX)nR$ 化简得$\boldsymbol{L nR-X}$含义从相遇点M走L步到达环入口从链表起点H走L步同样到达环入口。操作步骤快慢指针找到环内相遇点无环直接返回NULL。一个指针放在head一个指针放在相遇点。两个指针都每次走1步再次相遇的结点就是环入口。if(slow fast) { SListNode* meet slow; while(meet ! head) { meet meet-next; head head-next; } return meet; }易错点第二轮遍历两个指针必须同速不能一个走1步一个走2步。五、顺序表与链表对比对比项顺序表(动态数组)链表物理存储空间物理地址连续逻辑连续物理内存离散随机访问支持O(1)不支持遍历O(N)头部/中间增删需要移动元素O(N)拿到结点后修改指针O(1)查找结点O(N)空间扩容需要重新申请内存、拷贝释放存在空间浪费无容量概念每个结点附带指针存在额外内存开销缓存利用率高内存连续CPU缓存预取命中率高低结点分散容易缓存失效适用场景频繁查询、按下标访问频繁头部/中间插入删除长度波动大重要提醒链表增删O(1)的前提是已经拿到目标结点地址如果需要遍历查找结点整体复杂度依旧是O(N)。CPU缓存小知识点CPU读取内存会一次性读取一整条缓存行。顺序表内存连续读取一个元素会预加载后续一批数据链表结点分散每次访问结点都可能访问内存大数据量性能差距明显。 
长河君 · 2026/10/29 2:07:37 · 阅读 1.2k 数据结构：链表
一、链表概念链表属于线性表逻辑上元素是连续序列但物理内存不一定连续。 链表由一个个结点组成每个结点分为两部分数据域存储有效数据指针域存储下一个结点的地址依靠指针把结点串接起来结点从堆上动态malloc申请两次申请的内存地址可以连续也可以不连续由操作系统分配。通俗理解顺序表相当于电影院连续连号座位链表相当于人分散各处每个人保存下一个人的位置信息。二、链表的8种组合分类三组特征自由组合一共8种链表单向 / 双向带头结点 / 不带头结点循环 / 非循环笔试、工程实际只重点掌握2种1. 无头单向非循环链表笔试OJ高频typedef int SLTDateType; typedef struct SListNode { SLTDateType data; struct SListNode* next; }SListNode;只能向后遍历无法回退无哨兵头结点。应用很少单独存储业务数据多用于哈希桶、图邻接表大量出现在笔试题。坑点头插、头删会改变链表头指针函数需要传二级指针。2. 带头双向循环链表工程实际常用typedef int LTDataType; typedef struct ListNode { LTDataType _data; struct ListNode* next; struct ListNode* prev; }ListNode;存在哨兵头结点不存有效数据尾结点next指向头头结点prev指向尾。结构看着复杂但编码简单空链表、头结点、尾结点不需要特殊边界处理。总结考试刷题重点考无头单向非循环链表实际开发优先带头双向循环链表。三、单链表基础接口考点基础接口BuySListNode申请结点、打印、头插、尾插、头删、尾删、查找、SListInsertAfter、SListEraseAfter。考点为什么单链表多用pos之后插入/删除很少在pos之前操作 单链表没有前驱指针在pos前面插入需要从头遍历找pos的前一个结点时间复杂度O(N)在pos后面插入删除直接修改指针O(1)即可完成。四、链表经典OJ考点删除链表中等于val的所有结点反转单链表求链表中间结点快慢指针slow走1步fast走2步fast到末尾slow即为中间结点求链表倒数第k个结点合并两个有序链表按照x分割链表判断链表回文结构求两个链表第一个相交结点注意相交判断看结点地址是否相等不是看存储的数据值一旦相交后续结点全部共用。1. 判断链表是否有环 LeetCode141快慢指针slow一次走1步fast一次走2步都从head出发。有环快慢指针一定会在环内相遇无环fast走到NULL结束。面试问答为什么fast走2步、slow走1步一定能追上fast走3步行不行 环内相对速度为1每次两者距离减1最终必定相遇。 如果fast走3步相对速度为2若环内初始间隔是奇数会直接跨过慢指针永远无法相遇。2. 寻找入环的第一个结点 LeetCode142⚠️重要快慢指针相遇点不等于环入口。公式推导 L起点H到环入口E距离X入口E到相遇点M距离R环的总长度 slow路程$(LX)$ fast路程$2((LX))(LX)nR$ 化简得$\boldsymbol{L nR-X}$含义从相遇点M走L步到达环入口从链表起点H走L步同样到达环入口。操作步骤快慢指针找到环内相遇点无环直接返回NULL。一个指针放在head一个指针放在相遇点。两个指针都每次走1步再次相遇的结点就是环入口。if(slow fast) { SListNode* meet slow; while(meet ! head) { meet meet-next; head head-next; } return meet; }易错点第二轮遍历两个指针必须同速不能一个走1步一个走2步。五、顺序表与链表对比对比项顺序表(动态数组)链表物理存储空间物理地址连续逻辑连续物理内存离散随机访问支持O(1)不支持遍历O(N)头部/中间增删需要移动元素O(N)拿到结点后修改指针O(1)查找结点O(N)空间扩容需要重新申请内存、拷贝释放存在空间浪费无容量概念每个结点附带指针存在额外内存开销缓存利用率高内存连续CPU缓存预取命中率高低结点分散容易缓存失效适用场景频繁查询、按下标访问频繁头部/中间插入删除长度波动大重要提醒链表增删O(1)的前提是已经拿到目标结点地址如果需要遍历查找结点整体复杂度依旧是O(N)。CPU缓存小知识点CPU读取内存会一次性读取一整条缓存行。顺序表内存连续读取一个元素会预加载后续一批数据链表结点分散每次访问结点都可能访问内存大数据量性能差距明显。