一【题目类别】

链表

二【题目难度】

简单

三【题目编号】

203.移除链表元素

四【题目描述】

给你一个链表的头节点 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 , 1 0 4 ] [0, 10^4] [0,104]内 1 <= Node.val <= 50 0 <= val <= 50

七【解题思路】

这类题的做法有很多，可以设置两个指针遍历整个链表，但是这样代码比较冗长，还需要判断第一个结点的值。所以这道题我采用一个“虚拟结点”，用这个“虚拟结点”指向头结点，然后以“虚拟结点”的下一个结点，也就是头结点开始遍历搜索，遇到值相等的可以直接断链，最后返回“虚拟结点”下一个结点就是符合要求的链表头结点

八【时间频度】

时间复杂度： O ( n ) O(n) O(n)，其中 n n n为链表长度

九【代码实现】

1. Java语言版

package LinkedList;

public class p203_RemoveLinkedListElements {
          
   

    int val;
    p203_RemoveLinkedListElements next;

    public p203_RemoveLinkedListElements() {
          
   
    }

    public p203_RemoveLinkedListElements(int val) {
          
   
        this.val = val;
    }

    public p203_RemoveLinkedListElements(int val, p203_RemoveLinkedListElements next) {
          
   
        this.val = val;
        this.next = next;
    }

    public static void main(String[] args) {
          
   
        p203_RemoveLinkedListElements node1 = new p203_RemoveLinkedListElements(1);
        p203_RemoveLinkedListElements node2 = new p203_RemoveLinkedListElements(2);
        p203_RemoveLinkedListElements node3 = new p203_RemoveLinkedListElements(6);
        p203_RemoveLinkedListElements node4 = new p203_RemoveLinkedListElements(3);
        p203_RemoveLinkedListElements node5 = new p203_RemoveLinkedListElements(4);
        p203_RemoveLinkedListElements node6 = new p203_RemoveLinkedListElements(5);
        p203_RemoveLinkedListElements node7 = new p203_RemoveLinkedListElements(6);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        node6.next = node7;
        node7.next = null;
        p203_RemoveLinkedListElements res = removeElements(node1, 6);
        while (res != null) {
          
   
            if (res.next != null) {
          
   
                System.out.print(res.val + "->");
            } else {
          
   
                System.out.print(res.val);
            }
            res = res.next;
        }
    }

    public static p203_RemoveLinkedListElements removeElements(p203_RemoveLinkedListElements head, int val) {
          
   
        p203_RemoveLinkedListElements fakeNode = new p203_RemoveLinkedListElements(-1);
        fakeNode.next = head;
        p203_RemoveLinkedListElements p = fakeNode;
        while (p.next != null) {
          
   
            if (p.next.val == val) {
          
   
                p.next = p.next.next;
            } else {
          
   
                p = p.next;
            }
        }
        return fakeNode.next;
    }

}

2. C语言版

#include<stdio.h>
#include<stdlib.h>

struct ListNode
{
          
   
	int val;
	struct ListNode *next;
};

struct ListNode* removeElements(struct ListNode* head, int val)
{
          
   
	struct ListNode* fakeNode = (struct ListNode*)malloc(sizeof(struct ListNode));
	fakeNode->val = -1;
	fakeNode->next = head;
	struct ListNode* p = fakeNode;
	while (p->next != NULL)
	{
          
   
		if (p->next->val == val)
		{
          
   
			p->next = p->next->next;
		}
		else
		{
          
   
			p = p->next;
		}
	}
	return fakeNode->next;
}

/*主函数省略*/

十【提交结果】

1. Java语言版
2. C语言版