Leetcode 203.移除链表元素（画图分析）

力扣传送门(opens new window)

题意：删除链表中等于给定值 val 的所有节点。

示例 1： 输入：head = [1,2,6,3,4,5,6], val = 6 输出：[1,2,3,4,5]

示例 2： 输入：head = [], val = 1 输出：[]

示例 3： 输入：head = [7,7,7,7], val = 7 输出：[]

解题思路：

1. 使用虚拟头节点 (dummy node)：

• 链表的第一个节点可能需要被删除，所以为了方便处理头节点的特殊情况，我们创建一个虚拟头节点 (dummy)。
• 这个虚拟头节点不是真正存在于链表中的，它只是帮助我们简化操作，尤其是当链表的第一个节点需要删除时，直接从虚拟节点操作比较方便。

2. 遍历链表并删除指定节点：
   • 我们使用一个指针 currNode 从虚拟头节点开始，一直往后遍历链表。
   • 在每个节点上，我们检查当前节点的下一个节点的值是否等于 val。如果是，我们就“跳过”这个节点，让当前节点直接指向它的下下个节点，完成删除。
   • 如果下一个节点的值不是 val，我们继续往后移动指针。
3. 返回结果：
   • 当遍历完成后，我们返回 dummy.next，即链表的真正头节点（注意：可能头节点已经被删除，因此返回虚拟头节点的下一个节点更安全）。

代码实现：

虚拟头结点

class Solution {
    // 定义一个方法，用于从链表中移除所有值等于 val 的节点
    public ListNode removeElements(ListNode head, int val) {
        // 创建一个虚拟头节点，值为 -1，方便处理头节点被删除的情况
        ListNode dummy = new ListNode(-1);
  
        // 将虚拟头节点的下一个节点指向链表的实际头节点
        dummy.next = head;
  
        // 初始化当前节点为虚拟头节点
        ListNode currNode = dummy;
  
        // 开始遍历链表，直到当前节点的下一个节点为空
        while(currNode.next != null){
            // 如果当前节点的下一个节点的值等于目标值 val
            if(currNode.next.val == val){
                // 跳过下一个节点，将当前节点的下一个节点指向下下个节点
                currNode.next = currNode.next.next;
            } else {
                // 如果下一个节点的值不等于目标值，继续遍历下一个节点
                currNode = currNode.next;
            }
        }
  
        // 返回去掉目标值节点后的链表头节点（即虚拟头节点的下一个节点）
        return dummy.next;
    }
}

递归

class Solution {
    // 定义一个方法，用于从链表中递归移除所有值等于 val 的节点
    public ListNode removeElements(ListNode head, int val) {
        // 如果当前节点为空，直接返回 null（递归结束条件）
        if (head == null)
            return null;
  
        // 递归调用 removeElements 方法，处理当前节点的下一个节点
        head.next = removeElements(head.next, val);
  
        // 如果当前节点的值等于目标值 val
        if (head.val == val) {
            // 返回当前节点的下一个节点（即删除当前节点）
            return head.next;
        } else {
            // 如果当前节点的值不等于目标值，返回当前节点
            return head;
        }
    }
}

python

class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val  # 节点的值
        self.next = next  # 指向下一个节点的指针

class Solution:
    # 定义一个方法，用于从链表中移除所有值等于 val 的节点
    def removeElements(self, head: ListNode, val: int) -> ListNode:
        # 创建一个虚拟头节点，值为 -1，方便处理头节点被删除的情况
        dummy = ListNode(-1)
  
        # 将虚拟头节点的下一个节点指向链表的实际头节点
        dummy.next = head
  
        # 初始化当前节点为虚拟头节点
        currNode = dummy
  
        # 开始遍历链表，直到当前节点的下一个节点为空
        while currNode.next is not None:
            # 如果当前节点的下一个节点的值等于目标值 val
            if currNode.next.val == val:
                # 跳过下一个节点，将当前节点的下一个节点指向下下个节点
                currNode.next = currNode.next.next
            else:
                # 如果下一个节点的值不等于目标值，继续遍历下一个节点
                currNode = currNode.next
  
        # 返回去掉目标值节点后的链表头节点（即虚拟头节点的下一个节点）
        return dummy.next

c++

#include <iostream>

// 定义链表节点结构
struct 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) {}  
};

class Solution {
public:
    // 定义一个方法，用于从链表中移除所有值等于 val 的节点
    ListNode* removeElements(ListNode* head, int val) {
        // 创建一个虚拟头节点，值为 -1，方便处理头节点被删除的情况
        ListNode* dummy = new ListNode(-1);
  
        // 将虚拟头节点的下一个节点指向链表的实际头节点
        dummy->next = head;
  
        // 初始化当前节点为虚拟头节点
        ListNode* currNode = dummy;
  
        // 开始遍历链表，直到当前节点的下一个节点为空
        while (currNode->next != nullptr) {
            // 如果当前节点的下一个节点的值等于目标值 val
            if (currNode->next->val == val) {
                // 跳过下一个节点，将当前节点的下一个节点指向下下个节点
                currNode->next = currNode->next->next;
            } else {
                // 如果下一个节点的值不等于目标值，继续遍历下一个节点
                currNode = currNode->next;
            }
        }
  
        // 返回去掉目标值节点后的链表头节点（即虚拟头节点的下一个节点）
        return dummy->next;
    }
};

时间复杂度分析：

在这道题中，咱们主要的操作是遍历链表，并在遍历时决定是否删除节点。让我们逐步分析一下：

1. 遍历链表：整个链表会从头到尾遍历一遍。在遍历过程中，我们对每个节点只做了常数次操作（检查节点值，调整指针等）。假设链表有 n 个节点，那么我们需要遍历 n 次。因此，遍历链表的时间复杂度是 O(n)。
2. 删除节点的操作：删除操作实际上只是改变指针的指向，并不涉及额外的循环或递归。因此，在遍历的过程中删除节点不会影响时间复杂度，每个节点只会被访问一次。

综上所述，链表遍历的时间复杂度是 O(n)。

空间复杂度分析：

1. 额外的空间：在这个算法中，我们只创建了一个虚拟头节点 dummy 和一个指针 currNode，这些变量都只占用了常量的额外空间（即 O(1) 空间）。
2. 递归或额外数据结构：我们并没有使用递归，也没有使用额外的复杂数据结构（如栈、队列等）来存储数据。所有的操作都是在原链表上进行的，且没有动态分配额外的存储空间。

所以，算法的空间复杂度是 O(1)，因为只需要常量级的额外空间。

总结：

• 时间复杂度: O(n)，因为需要遍历链表中的所有节点。
• 空间复杂度: O(1)，因为只使用了常量级别的额外空间。