数据结构实战：移除链表元素

数据结构实战：移除链表元素

从零开始掌握链表节点删除技巧

在数据结构的学习中，链表是最基础且最重要的线性结构之一。本文将围绕“移除链表元素”这一经典问题，为你详细讲解如何删除链表中所有值为指定元素的节点。无论你是刚接触链表的小白，还是准备面试的开发者，都能从中受益。

什么是链表？

链表是一种物理存储单元上非连续、非顺序的线性结构，由一系列节点（Node）组成。每个节点包含两部分：数据域（存储元素值）和指针域（指向下一个节点的引用）。由于不需要连续内存，链表的插入和删除操作非常高效，但查找需要遍历。

问题描述

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回新的头节点。例如：输入: 1->2->6->3->4->5->6, val = 6，输出: 1->2->3->4->5。

思路分析

解决链表删除操作的核心是遍历链表，找到待删除节点的前一个节点，修改其指针指向待删除节点的下一个节点。但有一个特殊情况：如果头节点本身就是要删除的节点，我们需要特殊处理。为了简化代码，我们引入虚拟头节点（dummy node），它指向原链表的头节点，这样头节点就变成了普通节点，无需单独处理。

代码实现（Python）

class ListNode:    def init(self, val=0, next=None):        self.val = val        self.next = nextdef removeElements(head: ListNode, val: int) -> ListNode:    # 创建虚拟头节点    dummy = ListNode(0)    dummy.next = head    current = dummy        while current.next:        if current.next.val == val:            # 删除current.next节点            current.next = current.next.next        else:            current = current.next    return dummy.next    

边界情况处理

• 空链表：直接返回None。
• 头节点就是要删除的值：虚拟头节点让处理统一。
• 连续多个要删除的节点：while循环会连续跳过。
• 所有节点都要删除：最后返回None。

复杂度分析

时间复杂度：O(n)，只需遍历一次链表。 空间复杂度：O(1)，只使用了常数额外空间。

总结

通过本文，你学会了如何使用虚拟头节点优雅地解决移除链表元素问题。这是数据结构中链表删除操作的经典技巧，务必熟练掌握。希望这个教程对你有所帮助！

—— 数据结构系列教程 · 链表篇