[数据结构与算法]移除链表元素

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

思路之一：
注意：
要考虑链表为空，运行结果为空，链表只有一个节点等情况
错误示例：

#include<stdio.h>
#include<stdlib.h>
struct ListNode 
{
    int val;
    struct ListNode *next; 
};
struct ListNode* removeElements(struct ListNode* head, int val){
	struct ListNode* cur, *newhead, *tail;
	tail = NULL;
	newhead = NULL;
	cur = head;
	if (head == NULL)
		return NULL;
	while (cur)
	{
		if (cur->val != val)
		{
			if (newhead == NULL)
			{
				newhead = cur;
				tail = cur;
				cur = cur->next;
			}
			else
			{
				tail->next = cur;
				tail = cur;
				cur = cur->next;
			}
		}
		else
		{
			cur = cur->next;
		}
	}
	if (tail)
		tail->next = NULL;
	return newhead;
}
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 = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* plist = n1;
	removeElements(plist,3);

}

以上代码可以通过oj，但是内存泄漏的问题需要解决，代码风格也可以优化。

正确示例

#include<stdio.h>
#include<stdlib.h>
struct ListNode
{
	int val;
	struct ListNode *next;
};
struct ListNode* removeElements(struct ListNode* head, int val){
	if (head == NULL)
		return NULL;
	struct ListNode* cur = head;
	struct ListNode* newhead = NULL, *tail = NULL;
	while (cur)
	{
		//如果值是val，需要free对应的节点，
		//对应的next也被释放，难以找到下个节点，所以将下一个节点存下来
		struct ListNode* next = cur->next;
		if (cur->val != val)
		{
			if (newhead == NULL)
			{
				newhead = cur;
				tail = cur;
			}
			else
			{
				tail->next = cur;
				tail = cur;
			}
		}
		else
		{
			free(cur);
		}
		cur = next;
	}
	if (tail)
		tail->next = NULL;
	return newhead;
}
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 = 1;
	n2->val = 2;
	n3->val = 3;
	n4->val = 4;
	n1->next = n2;
	n2->next = n3;
	n3->next = n4;
	n4->next = NULL;

	struct ListNode* plist = n1;
	removeElements(plist, 3);

}

运行结果
如图
运行后节点n3被释放，链表变为n1->n2->n4->NULL