移除链表元素 ＜难度系数⭐＞

1.移除链表元素 ＜难度系数⭐＞

📝 题述：给你一个链表的头节点 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
输出：[ ]

🧷 平台：Visual studio 2017 && windows

🔑 核心思想：
思路1，双指针，cur找到val值所在的节点，prev记录前一个位置，依次删除，细节请看下图：

思路2，新链表，把链表中所有不是val的值尾插至新链表，删除val的节点

leetcode原题

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

typedef int SLTDataType;

struct ListNode
{
	int val;
	struct ListNode *next;
};
//思路1
struct ListNode* removeElements1(struct ListNode* head, int val)
{
	struct ListNode * cur = head;
	struct ListNode * prev = NULL;
	while (cur)//判断地址
	{
		//1、相等的情况
		if (cur->val == val)
		{
			if (cur == head)//1.1、第1个节点等于val时
			{
				head = head->next;
				free(cur);
				cur = head;
			}
			else//1.2、其它节点等于val时
			{
				prev->next = cur->next;
				free(cur);
				cur = prev->next;
			}
		}
		//2、不相等的情况
		else
		{
			prev = cur;
			cur = cur->next;
		}
	}
	return head;

}
//思路2
struct ListNode* removeElements2(struct ListNode* head, int val)
{	
	if(head == NULL)
		return NULL;
	//创建新节点
	struct ListNode* newhead = NULL, *tail = NULL;
	struct ListNode* cur = head;
	while(cur)
	{
		struct ListNode* next = cur->next;
		if(cur->val == val)
		{
			free(cur);
		}
		else
		{
			if(tail == NULL)
			{
				newhead = tail = cur;	
			}
			else
			{
				tail->next = cur;	
				tail = cur;
			}
		}
		cur = next;
	}
	if(tail)
		tail->next = NULL;
	return newhead;
}
int main()
{
	struct ListNode* n1 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n1->val = 1;

	struct ListNode* n2 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n2->val = 2;

	struct ListNode* n3 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n3->val = 6;

	struct ListNode* n4 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n4->val = 3;

	struct ListNode* n5 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n5->val = 4;

	struct ListNode* n6 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n6->val = 5;

	struct ListNode* n7 = (struct ListNode*)malloc(sizeof(struct ListNode));
	n7->val = 6;

	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = n5;
	n5->next = n6;
	n6->next = n7;
	n7->next = NULL;

	removeElements1(n1, 6);
	removeElements2(n1, 6);
	return 0;
}