本篇核心知识链表基础、链表常用操作清空、交换、单链表经典题求长度、反转、查找倒数第 K 个节点、快慢指针、递归逆序打印、链表判环 / 求环长、链表相交、指定节点 O (1) 删除、栈结构简介一、链表基础概念链表是链式线性结构内存不连续依靠指针将多个节点串联。节点分为两大组成部分数据域存储业务数据指针域存储相邻节点地址单链表仅有后继指针next双向链表包含前驱prev 后继next。特性链表无固定容量可动态增删节点无需提前开辟连续内存不支持下标随机访问只能从头部开始逐一遍历分为(1)带头结点哨兵节点(2)不带头结点两种设计带头结点头结点不存有效数据统一空表、头部增删逻辑代码更简洁不带头结点首节点即为有效节点头部操作需要特殊判断。代码示例单链表基础节点定义#include iostream using namespace std; ​ // 单链表节点 struct Node { int data; // 数据域 Node* next; // 指针域指向后继节点 Node(int val) : data(val), next(nullptr) {} };二、链表基础操作清空、交换两个链表2.1 链表清空概念释放链表中所有堆节点内存防止内存泄漏最终将链表置为空表。特性逐个遍历有效节点调用delete释放带头链表仅清空有效节点保留哨兵头结点清空后将尾指针、后继指针置空避免野指针。代码示例// 清空带头单链表 void clear(Node* head) { Node* p head-next; while (p ! nullptr) { Node* temp p; p p-next; delete temp; // 逐个释放节点 } head-next nullptr; // 头结点后继置空链表为空 }2.2 交换两个链表概念交换两个链表的所有数据节点仅交换头尾指针不挪动节点、不拷贝数据。特性带头链表只需交换两个链表的头结点后继、尾指针即可效率极高单链表仅操作next指针双向链表需同步处理prev和next本质修改指针指向节点本身内存位置不变。代码示例交换两个带头单链表// 交换两个链表的有效节点 void swapList(Node* h1, Node* Node* h2) { // 临时指针中转 Node* temp h1-next; h1-next h2-next; h2-next temp; }三、单链表经典算法面试高频3.1 求链表长度概念遍历链表所有有效节点统计节点总个数。特性时间复杂度(O(n))需要完整遍历一次链表遍历起点带头链表从head-next开始不带头链表直接从头指针开始空链表长度为 0。代码示例int getLength(Node* head) { int count 0; Node* p head-next; while (p ! nullptr) { count; p p-next; } return count; }3.2 单链表反转概念颠倒节点遍历顺序原尾节点变为首节点原首节点变为尾节点仅修改指针指向不修改数据。特性单链表仅能单向遍历常用两种实现方案头插法推荐逻辑简单三指针迭代法时间复杂度(O(n))反转后原链表失效。代码示例头插法反转void reverseList(Node* head) { Node* cur head-next; Node* newHead nullptr; while (cur ! nullptr) { Node* next cur-next; // 暂存后继节点 cur-next newHead; // 当前节点头插 newHead cur; cur next; } head-next newHead; // 重新挂载到哨兵头 }3.3 查找倒数第 K 个节点概念在单链表中定位倒数第 K 个节点快慢指针法是最优解法。特性基础解法先求总长度再正向遍历len-K步遍历两次链表快慢指针法双指针仅遍历一次效率更高快指针先走 K 步快慢指针同步向后移动快指针到末尾时慢指针即为倒数第 K 节点边界判断K 非法K≤0 / K 链表长度直接返回空。代码示例快慢指针版Node* findLastK(Node* head, int k) { if (k 0) return nullptr; Node* fast head-next; Node* slow head-next; ​ // 快指针先走k步 for (int i 0; i k fast ! nullptr; i) { fast fast-next; } // 步数不足K超过链表长度 if (fast nullptr i k) return nullptr; ​ // 快慢同步后移 while (fast ! nullptr) { fast fast-next; slow slow-next; } return slow; }3.4 查找链表中间节点概念利用快慢指针查找链表中间位置节点。特性慢指针每次走 1 步快指针每次走 2 步快指针走到末尾时慢指针指向中间节点链表长度为偶数得到靠右的中间节点。代码示例Node* findMid(Node* head) { Node* slow head-next; Node* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; } return slow; }3.5 从尾到头打印链表概念单链表只能正向遍历实现逆序打印常用递归法和栈结构。特性递归法利用函数调用栈先递归走到链表尾部回溯时打印无需额外空间栈法节点依次入栈再出栈打印先进后出特性递归深度过大易造成栈溢出。代码示例递归实现// 递归逆序打印 void printReverse(Node* p) { if (p nullptr) return; printReverse(p-next); // 先递归到尾部 cout p-data ; // 回溯时打印 } ​ // 调用方式 printReverse(head-next);3.6 单链表判环概念判断链表是否存在环形结构尾节点不再置空指向链表内部节点。特性核心解法快慢指针追击法逻辑无环时快指针必然先走到nullptr有环时快慢指针最终一定会相遇快指针步长 2慢指针步长 1。代码示例bool hasCycle(Node* head) { Node* slow head-next; Node* fast head-next; while (fast ! nullptr fast-next ! nullptr) { slow slow-next; fast fast-next-next; if (slow fast) // 指针相遇存在环 return true; } return false; // 快指针走到末尾无环 }3.7 求环的长度概念已知链表有环计算环内节点总个数。特性先利用快慢指针找到环内相遇点固定一个指针另一个指针继续遍历再次相遇时统计步数即为环长。代码示例int getCycleLen(Node* head) { if (!hasCycle(head)) return 0; Node* slow head-next; Node* fast head-next; // 找到相遇点 while (fast fast-next) { slow slow-next; fast fast-next-next; if (slow fast) break; } // 统计环长 int len 0; Node* p slow; do { p p-next; len; } while (p ! slow); return len; }3.8 判断两个单链表是否相交概念两个链表尾部节点指向同一个节点即为相交链表。特性核心结论两个相交单链表尾节点一定相同尾节点不同则必然不相交实现思路分别遍历到两个链表尾部对比尾指针地址。代码示例bool isIntersect(Node* h1, Node* h2) { Node* p1 h1-next; Node* p2 h2-next; // 遍历到尾节点 while (p1-next ! nullptr) p1 p1-next; while (p2-next ! nullptr) p2 p2-next; return p1 p2; // 尾节点地址相等则相交 }3.9 查找相交的第一个节点概念找到两个相交链表的首个公共节点两种主流解法。解法 1长度差值法推荐不修改节点结构分别求出两个链表长度长链表先走「长度差」步两个指针同步后第一个相等节点即为交点。代码示例Node* findInterNode(Node* h1, Node* h2) { int len1 getLength(h1); int len2 getLength(h2); Node* p1 h1-next; Node* p2 h2-next; // 长链表先走差值 if (len1 len2) { for (int i 0; i len1 - len2; i) p1 p1; } else { for (int i 0; i len2 - len1; i) p2 p2; } // 同步遍历找交点 while (p1 ! nullptr p2 ! nullptr) { if (p1 p2) return p1; p1 p1-next; p2 p2; } return nullptr; }解法 2标记计数法修改节点给每个节点增加计数标记遍历两个链表标记重复的节点即为交点缺点需要修改节点结构。3.10 O (1) 时间删除指定节点概念已知指向待删除节点的指针要求不遍历链表、以 (O(1)) 时间复杂度完成删除。特性单链表无法直接获取前驱节点不能常规摘链核心思路偷梁换柱将后继节点的数据拷贝到当前节点跳过后继节点释放原后继内存边界待删除节点为尾节点时仍需要遍历找前驱。代码示例// 传入待删除节点p非尾节点 void delNode(Node* p) { if (p nullptr || p-next nullptr) return; // 拷贝后继数据 p-data p-next-data; // 释放后继节点 Node* temp p-next; p-next p-next-next; delete temp; }拓展该算法仅适用于非尾节点若为尾节点必须正向遍历找到前驱节点才能删除。四、栈结构简介概念栈是受限线性表遵循先进后出FILO规则仅允许在栈顶进行插入入栈、删除出栈操作。特性操作端口唯一所有操作仅限栈顶实现方式顺序表数组、链表均可实现栈典型应用递归调用、表达式求值、逆序操作链表逆序打印。代码示例链式栈简易实现struct StackNode { int data; StackNode* next; StackNode(int val):data(val),next(nullptr){} }; // 入栈 void push(StackNode* top, int val) { StackNode* newNode new StackNode(val); newNode-next top; top newNode; } // 出栈 void pop(StackNode* top) { if (top nullptr) return; StackNode* temp top; top top-next; delete temp; }五、拓展总结 考点梳理快慢指针链表高频考点用于求中间节点、倒数 K 节点、链表判环核心是步长差异递归适合单链表逆序打印注意递归深度限制O (1) 删除节点单链表经典巧解利用数据拷贝规避找前驱的问题链表相交 / 判环笔试、面试必考优先使用长度差、快慢指针标准解法链表操作核心原则操作指针前先暂存后继节点防止断链使用完毕及时delete避免内存泄漏。