【C++复习】链表

很多小伙伴刷算法题时，链表永远是第一道坎！

数组可以随机访问，链表只能遍历，指针一转错、断链、野指针，直接全盘崩盘😭

为了帮大家彻底吃透链表，今天整理一份**「C++链表全套复习题」**

从结构体构建链表 → 基础增删查改 → 进阶反转/找环/找中点/去重

难度循序渐进，全部是笔试面试高频原题，适合期末复习、算法入门、刷题打底✅

全篇代码可直接编译运行，建议收藏保存，反复默写吃透！

📌 一、链表核心认知

链表是非连续、动态内存的线性结构

核心考点：

• 不支持随机访问，必须从头遍历

• 插入/删除效率极高（仅改指针）

• 重点考察：指针操作、断链保护、虚拟头结点

📌 二、基础铺垫：结构体构建链表节点

所有链表操作的基础，标准 C++ 单链表节点定义：

// 定义单链表节点structListNode{intval;// 节点数据ListNode*next;// 指向下一节点指针// 构造函数ListNode(intx):val(x),next(nullptr){}};

📌 三、封装链表类（含全部基础操作）

统一封装常用接口，复习更系统，适配所有基础题型：

classLinkList{private:ListNode*head;// 链表头结点public:// 构造函数：初始化空链表LinkList(){head=nullptr;}// 1. 获取链表长度intgetLength(){intlen=0;ListNode*p=head;while(p!=nullptr){len++;p=p->next;}returnlen;}// 2. 按值查找元素，返回节点ListNode*findVal(intval){ListNode*p=head;while(p!=nullptr){if(p->val==val)returnp;p=p->next;}returnnullptr;// 未找到}// 3. 尾部插入节点voidinsertTail(intval){ListNode*newNode=newListNode(val);// 空链表直接赋值头节点if(head==nullptr){head=newNode;return;}// 遍历到尾部插入ListNode*p=head;while(p->next!=nullptr){p=p->next;}p->next=newNode;}// 4. 头部插入节点voidinsertHead(intval){ListNode*newNode=newListNode(val);newNode->next=head;head=newNode;}// 5. 指定位置插入节点（pos从0开始）voidinsertPos(intpos,intval){intlen=getLength();if(pos<0||pos>len)return;// 位置非法// 插头部if(pos==0){insertHead(val);return;}ListNode*newNode=newListNode(val);ListNode*p=head;// 找到pos前一个节点for(inti=0;i<pos-1;i++){p=p->next;}newNode->next=p->next;p->next=newNode;}// 6. 按值删除节点voiddeleteVal(intval){if(head==nullptr)return;// 删除头节点if(head->val==val){ListNode*temp=head;head=head->next;deletetemp;return;}ListNode*p=head;// 找到待删除节点的前驱while(p->next!=nullptr&&p->next->val!=val){p=p->next;}if(p->next==nullptr)return;// 无目标节点ListNode*temp=p->next;p->next=temp->next;deletetemp;}// 7. 打印输出链表voidprintList(){ListNode*p=head;while(p!=nullptr){cout<<p->val<<" ";p=p->next;}cout<<endl;}};

✅ 以上是链表必考基础操作，期末选择题、基础编程题全覆盖

包含：增、删、查、长度计算、头尾插、指定位置插

📌 四、进阶高频面试操作（算法核心）

这部分是刷题、面试重点，全部独立可直接复用模板！

1. 链表反转（最常考）

ListNode*reverseList(ListNode*head){ListNode*pre=nullptr;ListNode*cur=head;// 迭代法：逐个反转指针while(cur!=nullptr){ListNode*next=cur->next;// 保存后继cur->next=pre;// 反转指向pre=cur;cur=next;}returnpre;// 新头节点}

2. 判断链表是否有环（快慢指针）

boolhasCycle(ListNode*head){ListNode*slow=head;ListNode*fast=head;// 慢指针走一步，快指针走两步while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;if(slow==fast)returntrue;// 相遇则有环}returnfalse;}

3. 寻找链表中间节点

ListNode*findMiddle(ListNode*head){ListNode*slow=head;ListNode*fast=head;// 快指针到底，慢指针停在中间while(fast!=nullptr&&fast->next!=nullptr){slow=slow->next;fast=fast->next->next;}returnslow;}

4. 删除链表重复节点（有序链表去重）

voiddeleteDuplicate(ListNode*head){if(head==nullptr)return;ListNode*p=head;while(p->next!=nullptr){// 相邻节点值相同则删除后继if(p->val==p->next->val){ListNode*temp=p->next;p->next=temp->next;deletetemp;}else{p=p->next;}}}

📌 五、复习总结（必背考点）

1.基础操作：头尾插入、指定位置插入、按值删除、遍历查找、求长度是所有链表题的地基，必须闭眼默写

2.进阶核心思想：

• 反转：迭代法双指针（最稳定、无栈溢出）

• 判环/找中点：快慢指针 「经典双指针思想」

• 去重：遍历比对，删除重复后继节点

3.易错点：空链表判断、删除节点后释放内存、指针断链、边界位置插入删除

💻 刷题建议

建议大家：先看懂逻辑 → 遮住代码默写 → 自己改测试用例

链表一旦熟练，后续树、图、哈希表刷题都会顺畅很多！

需要完整可直接运行的整合版源码 + 测试案例可以留言，我打包发给大家✨

#C++ #算法 #数据结构 #链表 #算法刷题 #期末复习 #编程学习 #计算机基础