203-移除链表元素

Doublew2w大约 2 分钟

给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == 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
 输出： []

提示：

列表中的节点数目在范围 [0, 10 ⁴] 内
1 <= Node.val <= 50
0 <= val <= 50

## 前置知识

链表
删除节点
虚拟节点

思路1:直接删除

先判断头结点的情况 $head != null \space \&\& \space head.val != val$
从当前节点的后驱节点进行遍历

关键点

头结点要特殊处理
$cur.next = cur.next.next$

代码

语言支持：Java

Java Code:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        // 删除值相同的头结点后，可能新的头结点也值相等，用循环解决
        while (head != null && head.val == val) {
            head = head.next;
        }
        if (head == null)
            return head;
        ListNode prev = head;
        // 确保当前结点后还有结点
        while (prev.next != null) {
            if (prev.next.val == val) {
                prev.next = prev.next.next;
            } else {
                prev = prev.next;
            }
        }
        return head;
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

思路2：虚拟头节点

关键点

在虚拟头节点下，要删除一个节点，删除方式一样。最后返回的时候是 $dummyNode.next$

代码


/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeElements(ListNode head, int val) {
        //创建一个虚拟头结点
        ListNode dummyNode=new ListNode(val-1);
        dummyNode.next=head;
        ListNode prev=dummyNode;
        //确保当前结点后还有结点
        while(prev.next!=null){
            if(prev.next.val==val){
                prev.next=prev.next.next;
            }else{
                prev=prev.next;
            }
        }
        return dummyNode.next;
    }
}

复杂度分析

令 n 为数组长度。

时间复杂度： $O(n)$
空间复杂度： $O(1)$

203-移除链表元素

题目地址(203. 移除链表元素 - 力扣（LeetCode）)

题目描述

思路1:直接删除

关键点

代码

思路2：虚拟头节点

关键点

代码