2025 高中信息技术数据结构链表的删除重复节点算法优化课件

一、知识铺垫：链表与重复节点问题的基础认知演讲人CONTENTS知识铺垫：链表与重复节点问题的基础认知2"删除重复节点"问题的定义与典型场景从暴力到优化：算法的演进路径深度辨析：不同算法的适用场景与教学重点实践提升：从理论到代码的落地训练总结与升华：算法优化的核心思想与学科价值目录2025高中信息技术数据结构链表的删除重复节点算法优化课件作为深耕高中信息技术教学十余年的一线教师，我始终认为：数据结构不仅是编程能力的基石，更是培养逻辑思维与算法优化意识的重要载体。链表作为线性表的动态存储结构，其操作涉及指针（或引用）的灵活运用，是高中阶段的教学难点与重点。而"删除链表中重复节点"这一经典问题，既涵盖了链表的基本操作，又能自然引出算法优化的核心思想，是提升学生"计算思维"素养的优质教学素材。今天，我将围绕这一主题，从知识铺垫、算法演进、优化策略到实践提升，展开系统讲解。01知识铺垫：链表与重复节点问题的基础认知1链表的核心特征与操作回顾要解决链表问题，首先需明确其底层结构。链表（LinkedList）是通过指针连接的节点序列，每个节点包含数据域（存储值）和指针域（指向下一个节点）。与数组的连续内存存储不同，链表的动态性使其在插入、删除操作上具备O(1)的理论时间复杂度（需已知前驱节点），但随机访问需O(n)时间。以单链表为例，其节点结构可表示为（以C++伪代码为例）：structListNode{intval;//数据域ListNode*next;//指针域ListNode(intx):val(x),next(nullptr){}//构造函数1链表的核心特征与操作回顾};在教学实践中，我常让学生用"火车车厢"类比：每节车厢（节点）装载货物（数据），并通过挂钩（指针）连接下一节车厢。这种具象化类比能有效降低抽象概念的理解门槛。022"删除重复节点"问题的定义与典型场景2"删除重复节点"问题的定义与典型场景所谓"删除重复节点"，指在链表中保留所有值唯一的节点，仅删除值重复出现的节点。根据删除程度的不同，问题可分为两类：保留一个重复节点：如链表1->2->2->3，处理后为1->2->3（保留第一个出现的重复节点）；删除所有重复节点：如链表1->2->2->3，处理后为1->3（所有重复值的节点均被删除）。这两类问题在实际场景中均有应用：例如学生成绩管理系统中，需去除重复录入的学号（保留一个）；或在数据清洗时，需删除所有重复的传感器读数（无保留）。明确问题边界是解决算法的第一步。03从暴力到优化：算法的演进路径1基础解法：双重遍历法（暴力法）对于高中阶段的学生，首次接触此类问题时，最直观的思路是"逐个检查每个节点，删除后续重复节点"。这一方法的实现步骤如下：步骤分解：固定当前节点：从头节点开始，遍历每个节点（记为curr）；遍历后续节点：以curr的下一个节点为起点（记为prev），再遍历其后的所有节点（记为temp）；比较与删除：若temp的值等于curr的值，将prev的next指向temp的next（跳过temp），完成删除；否则prev和temp同步后移；curr后移：当前节点处理完毕后，curr后移一位，重复上述过程直至链表末尾。代码示例（保留一个重复节点）：1基础解法：双重遍历法（暴力法）ListNode*removeDuplicates(ListNode*head){1if(head==nullptr)returnhead;//空链表直接返回2ListNode*curr=head;3while(curr!=nullptr){4ListNode*prev=curr;5ListNode*temp=curr-next;6while(temp!=nullptr){7if(temp-val==curr-val){81基础解法：双重遍历法（暴力法）prev-next=temp-next;//删除temp节点temp=prev-next;}else{prev=temp;temp=temp-next;}}curr=curr-next;}deletetemp;//释放内存（实际教学中可简化）1基础解法：双重遍历法（暴力法）returnhead;1}2复杂度分析：3时间复杂度：O(n²)（外层遍历n次，内层最多n次）；4空间复杂度：O(1)（仅使用常量额外空间）。5教学观察：学生在实现时易出现的错误包括：6未处理头节点为空的边界情况；7删除节点后未正确更新temp指针（如遗漏prev->next的重新赋值）；8内存泄漏（虽高中阶段不强调，但可作为拓展点）。92优化方向一：哈希表辅助法（空间换时间）暴力法的核心问题在于重复比较——每个节点都需与后续所有节点比较。若能快速判断某个值是否已出现过，可将内层遍历优化为O(1)查询。此时，哈希表（HashTable）成为理想选择。算法思路：遍历链表，用哈希表记录已出现的节点值；若当前节点值已在哈希表中，删除该节点；若未出现，则将值存入哈希表，继续遍历。代码示例（保留一个重复节点）：ListNode*removeDuplicatesOptimized(ListNode*head){2优化方向一：哈希表辅助法（空间换时间）if(head==nullptr)returnhead;1unordered_setintseen;//哈希表存储已出现的值2ListNode*dummy=newListNode(-1);//虚拟头节点简化操作3dummy-next=head;4ListNode*prev=dummy;5ListNode*curr=head;6while(curr!=nullptr){7if(seen.find(curr-val)!=seen.end()){8prev-next=curr-next;//删除当前节点92优化方向一：哈希表辅助法（空间换时间）01deletecurr;02}else{03seen.insert(curr-val);04prev=curr;05curr=curr-next;06}07}08ListNode*result=dummy-next;09deletedummy;//释放虚拟头节点10curr=prev-next;2优化方向一：哈希表辅助法（空间换时间）returnresult;}优化点分析：时间复杂度：O(n)（仅需一次遍历，哈希表查询/插入为O(1)）；空间复杂度：O(n)（最坏情况下存储所有不同值）；关键改进：通过空间换时间，将时间复杂度从O(n²)降至O(n)，适用于对时间要求高的场景（如实时数据处理）。教学提示：引入虚拟头节点（dummynode）是链表操作的常用技巧，可避免处理头节点被删除的特殊情况。我常提醒学生："虚拟头节点就像给链表戴了顶'安全帽'，让头节点的操作与其他节点统一化。"3优化方向二：排序后单指针遍历（时间换空间的折中）若题目对空间复杂度有严格限制（如O(1)），可考虑先对链表排序，使重复节点相邻，再通过一次遍历删除重复节点。算法思路：排序链表：使用归并排序（链表排序的最优选择，时间O(nlogn)，空间O(logn)递归栈）；遍历删除重复：排序后，重复节点必然相邻，只需比较当前节点与下一个节点的值，若相同则删除下一个节点，直至所有重复节点被处理。代码示例（保留一个重复节点）：//归并排序函数（简化版）ListNode*sortList(ListNode*head){3优化方向二：排序后单指针遍历（时间换空间的折中）if(head==nullptr||head-next==nullptr)returnhead;ListNode*slow=head;ListNode*fast=head-next;while(fast!=nullptrfast-next!=nullptr){slow=slow-next;fast=fast-next-next;}ListNode*mid=slow-next;3优化方向二：排序后单指针遍历（时间换空间的折中）slow-next=nullptr;//切断链表returnmerge(sortList(head),sortList(mid));}//合并两个有序链表ListNode*merge(ListNode*l1,ListNode*l2){ListNode*dummy=newListNode(-1);ListNode*curr=dummy;while(l1!=nullptrl2!=nullptr){3优化方向二：排序后单指针遍历（时间换空间的折中）if(l1-vall2-val){l1=l1-next;}else{curr-next=l2;l2=l2-next;}curr=curr-next;}curr-next=(l1!=nullptr)?l1:l2;curr-next=l1;3优化方向二：排序后单指针遍历（时间换空间的折中）ListNode*result=dummy-next;deletedummy;returnresult;}//排序后删除重复节点ListNode*removeDuplicatesAfterSort(ListNode*head){if(head==nullptr)returnhead;ListNode*sorted=sortList(head);ListNode*curr=sorted;3优化方向二：排序后单指针遍历（时间换空间的折中）while(curr-next!=nullptr){ListNode*temp=curr-next;curr-next=temp-next;deletetemp;}else{curr=curr-next;}}returnsorted;if(curr-val==curr-next-val){3优化方向二：排序后单指针遍历（时间换空间的折中）}复杂度分析：时间复杂度：O(nlogn)（排序的时间主导）；空间复杂度：O(logn)（归并排序的递归栈空间）。适用场景：当内存受限（无法使用哈希表）但时间要求优于O(n²)时，此方法是折中选择。例如嵌入式设备处理传感器数据时，内存有限但需较高效率。04深度辨析：不同算法的适用场景与教学重点1算法选择的核心依据实际问题中，算法的选择需综合考虑以下因素：数据规模：当n较小时（如n<1000），暴力法的O(n²)与优化法的O(n)差异不显著；但n>10⁴时，O(n²)可能导致超时；空间限制：哈希表法需O(n)空间，若题目明确要求"原地修改"（如LeetCode83题的部分变种），则需选择排序法或暴力法；链表特性：若链表本身接近有序（如插入时已排序），则排序法的额外时间可忽略，此时直接单指针遍历更高效。2教学中需突破的三大难点根据多年教学经验，学生在掌握该问题时易卡在以下环节：指针操作的复杂性：链表的删除操作需同时修改前驱节点的指针，学生常因忘记保存前驱节点（如直接使用curr->next=curr->next->next而不处理前驱）导致断链；应对策略：通过"指针追踪图"辅助理解——在黑板上画出链表节点的内存布局，用不同颜色标记curr、prev、temp的指向，动态演示删除过程；边界条件的处理：头节点/尾节点被删除的情况（如链表1->1->2，删除头节点后新头节点为2）；应对策略：强制使用虚拟头节点，将头节点操作与其他节点统一化，减少特殊判断；算法优化意识的培养：部分学生满足于写出暴力法，缺乏主动优化的意识；2教学中需突破的三大难点应对策略：通过"时间测试实验"强化认知——用Python编写暴力法与哈希表法，输入n=10⁴的随机链表，观察运行时间差异（通常暴力法需数秒，哈希表法仅需毫秒级），直观感受优化的价值。05实践提升：从理论到代码的落地训练1典型例题精讲例题：给定一个无序单链表（如1->3->2->3->1），要求删除所有重复节点（即任何出现次数≥2的节点值均被删除），最终链表为2（假设原题要求删除所有重复节点）。解法思路（哈希表统计频次+二次遍历）：第一次遍历：用哈希表统计每个值的出现次数；第二次遍历：保留频次为1的节点，删除频次≥2的节点。代码实现：ListNode*removeAllDuplicates(ListNode*head){if(head==nullptr)returnhead;1典型例题精讲unordered_mapint,intcount;//第一次遍历统计频次while(curr!=nullptr){count[curr-val]++;curr=curr-next;}//第二次遍历删除重复节点ListNode*dummy=newListNode(-1);dummy-next=head;ListNode*curr=head;1典型例题精讲01curr=dummy;02if(count[curr-next-val]1){03ListNode*temp=curr-next;04curr-next=temp-next;05deletetemp;06}else{07curr=curr-next;08}09}10while(curr-next!=nullptr){1典型例题精讲ListNode*result=dummy-next;deletedummy;returnresult;}030402012学生常见错误案例在实验课中，我收集了学生的典型错误，整理如下：|错误类型|示例代码片段|错误原因分析||-------------------------|-----------------------------------------------|-----------------------------------------------------------------------------||未处理空链表|while(curr-next!=nullptr)|当head为空时，curr为nullptr，访问curr->next会导致空指针异常|2学生常见错误案例|删除节点后未更新指针|if(temp-val==curr-val){temp=temp-next;}|仅移动temp而未修改prev->next，导致链表未实际删除节点||哈希表键值统计错误|count[curr-val]=1;|应使用count[curr-val]++累加频次，而非直接赋值1||内存泄漏|未释放被删除节点的内存|高中阶段虽不强制，但可作为编程规范意识培养的切入点|3拓展训练建议为深化理解，可设计以下分层任务：进阶层：将哈希表法改为