您现在的位置是：首页 >技术杂谈 >【数据结构】--单链表力扣面试题①移除链表元素网站首页技术杂谈

题述：

给你一个链表的头结点head和一个整数val,请你删除链表中所有满足Node.val == val的节点，并返回新的头结点。

思考：

为什么说要返回新的头结点，因为你删除的可能存在把原来的头结点删除的情况，这时就需要有新的头结点。这道题其实就是考察增删查改的变形。

思路：

1、想删除值是val的那一个，那就要先找到它，这个节点值域是val的那一个节点可能有好几个。

2、因为涉及删除某一个节点，那就一定要使被删除节点的前一个节点的指针域指向被删除节点原指向的下一节点。所以重点是找到被删除节点的前驱节点。法一就是找要被删除的前一个节点，判断他的next指向的下一节点的值域是不是val值。法二就是定义两个指针，一个指向前，一个指向后。我们推荐法二。因为如果省几个变量来节省内存是没必要的，并不是没有考虑空间复杂度的问题，而是因为多定义几个变量，空间复杂度还是o(1)。相对来说法二在实现中会更清晰一点。

注意点：头删和中间删除节点的情况要分别考虑

如果是头删就不需要prev指针，因为prev初始化是NULL，而你写成prev->next就对空指针访问了，这是非法访问内存的行为，是不被允许的！因此只需要考虑cur怎么动。

如果是中间删除需要prev指针了，因为其指针域也需要跟着改变。

 最后代码如下：

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

struct ListNode
{
	int val;
	struct ListNode* next;
};
struct ListNode* removeElements(struct ListNode* head,int val)
{
	struct ListNode* prev = NULL, * cur = head;//遍历肯定要用cur去遍历
	while (cur)
	{
		if (cur->val == val)
		{	//1、头删，如果第一个节点数据就=val了
			if (cur == head)
			{
				head = cur->next;
				free(cur);
				cur = head;
				//这里头删是不用管prev的，因为后续不相等prev会=cur
			}
			//2、中间删除的情况处理
			else
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}
		}
		else
		{	//不相等则循环遍历往下走
			prev = cur;//不要写prev=prev->next,因为prev可能有是NULL的情况
			cur = cur->next;
		}
	}
	return head;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 7;
	n2->val = 7;
	n3->val = 7;
	n4->val = 7;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* head = removeElements(n1, 7);

	return 0;
}