链表基础与虚拟头结点 ——203. 移除链表元素

一、今日学习总结今天正式进入链表模块的学习。链表是一种与数组截然不同的数据结构其节点在内存中不连续通过指针引用连接。核心任务是 LeetCode 203「移除链表元素」。这道题看似简单却完美揭示了链表操作的一个关键技巧——虚拟头结点Dummy Node。使用虚拟头结点可以统一处理头结点和普通节点的删除逻辑避免繁琐的特殊判断。二、链表基础回顾1. 链表结构示意text头结点 ↓ ┌───┬───┐ ┌───┬───┐ ┌───┬───┐ │ 1 │ ●─┼──→│ 2 │ ●─┼──→│ 3 │ ●─┼──→ NULL └───┴───┘ └───┴───┘ └───┴───┘ val next val next val next2. 数组 vs 链表对比特性数组链表内存分配连续内存非连续内存访问方式随机访问 O(1)顺序访问 O(n)插入/删除O(n)需要移动元素O(1)已知前驱节点缓存友好性高低3. 链表节点定义cppstruct ListNode { int val; ListNode *next; ListNode() : val(0), next(nullptr) {} ListNode(int x) : val(x), next(nullptr) {} ListNode(int x, ListNode *next) : val(x), next(next) {} };三、题目详解题目描述给你一个链表的头节点head和一个整数val请你删除链表中所有满足Node.val val的节点并返回新的头节点。示例text输入head [1,2,6,3,4,5,6], val 6 输出[1,2,3,4,5]四、解题思路4.1 核心难点头结点的特殊性在链表中删除普通节点只需要textprev-next curr-next;但要删除头结点时情况不同头结点没有前驱节点删除后需要更新头指针如果单独处理头结点代码会变得冗长且容易出错。4.2 解决方案虚拟头结点在真正的头结点前面添加一个虚拟节点它的next指向head。textdummy → 1 → 2 → 6 → 3 → ... ↑ newHead (dummy-next)优势原来的头结点现在有了前驱dummy所有节点的删除逻辑完全统一最后返回dummy-next即可4.3 算法步骤创建虚拟头结点dummy其next指向head初始化prev dummycurr head遍历链表若curr-val val删除currprev-next curr-next若不等移动prev curr移动curr curr-next返回dummy-next