题解 | #移除链表元素#

题目链接

移除链表元素

题目描述

给定一个链表的头节点 head 和一个整数 val，请你删除链表中所有值为 val 的节点，并返回新链表的头节点。

这是一个核心代码模式 (Core Code Mode) 的题目，你只需要实现 removeElements 函数即可。

示例: 输入: head = {1,2,6,3,4,5,6}, val = 6

输出: {1,2,3,4,5}

解题思路

删除链表节点时，最棘手的情况是需要删除头节点，因为这会改变链表的入口。为了统一处理所有节点（无论是头节点还是中间节点），我们可以使用一个虚拟头节点 (Dummy Node)。

使用虚拟头节点

基本思想：创建一个虚拟节点 dummy，让它的 next 指向原始的头节点 head。这样一来，原始链表中的所有节点（包括头节点）都有一个前驱节点，删除操作就变得统一了。我们始终可以从 dummy 节点开始遍历。
算法步骤:
1. 创建一个虚拟头节点 dummy，并使其指向 dummy.next = head。
2. 创建一个指针 current，初始化为 dummy。这个指针将用来遍历链表，并始终位于我们正在检查的节点的前一个位置。
3. 循环遍历链表，当 current.next 不为空时： a. 如果 current.next 指向的节点的值等于 val，我们就需要删除它。这通过修改指针实现：current.next = current.next.next。这样就跳过了目标节点。 b. 如果 current.next 指向的节点的值不等于 val，说明这个节点应该保留。我们只需将 current 指针后移一位：current = current.next。
4. 循环结束后，dummy.next 就是新链表的头节点。返回 dummy.next 即可。

这个方法非常稳健，因为它优雅地处理了所有边界情况，例如：

链表为空 (head is null)。
所有节点都需要被删除。
头节点需要被删除。

代码

cpp
java
python

/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) : val(x), next(nullptr) {}
};
*/
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param head ListNode类 
     * @param val int整型 
     * @return ListNode类
     */
    ListNode* removeElements(ListNode* head, int val) {
        // 创建虚拟头节点
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        
        ListNode* current = dummy;
        while (current->next != nullptr) {
            if (current->next->val == val) {
                // 删除节点
                ListNode* temp = current->next;
                current->next = current->next->next;
                delete temp; // 释放内存
            } else {
                current = current->next;
            }
        }
        
        ListNode* newHead = dummy->next;
        delete dummy; // 释放虚拟头节点的内存
        return newHead;
    }
};

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 *   public ListNode(int val) {
 *     this.val = val;
 *   }
 * }
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param head ListNode类 
     * @param val int整型
     * @return ListNode类
     */
    public ListNode removeElements(ListNode head, int val) {
        // 创建虚拟头节点
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        
        ListNode current = dummy;
        while (current.next != null) {
            if (current.next.val == val) {
                // 删除节点
                current.next = current.next.next;
            } else {
                current = current.next;
            }
        }
        
        return dummy.next;
    }
}

# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# @param head ListNode类 
# @param val int整型 
# @return ListNode类
#
class Solution:
    def removeElements(self , 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.next
            else:
                current = current.next
                
        return dummy.next

算法及复杂度

算法: 迭代 (使用虚拟头节点)
时间复杂度: $\mathcal{O}(N)$ ，其中 $N$ 是链表的节点数。我们只需要遍历链表一次。
空间复杂度: $\mathcal{O}(1)$ 。我们只使用了常数个额外的指针变量（dummy 和 current）。