题目

Remove all elements from a linked list of integers that have value val.

Example

Given: 1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 6

Return: 1 --> 2 --> 3 --> 4 --> 5

测试用例

1 --> 2 --> 6 --> 3 --> 4 --> 5 --> 6, val = 66 --> 6 --> 1, val = 66 --> 6 --> 6, val = 61 --> 2 --> 6 --> 6 --> 6 --> 5 --> 6, val = 6

解析

这道题给出三种算法

第一种：

直接两个指针pre和cur，一前一后，相互挨着，cur指针遇到val后，pre的next直接指向cur的下一个指针，同时cur也向后移动一个。

第二种：

把指定的元素看成雷区，cur指针进入雷区后，pre停止并等待cur出雷区，同时pre的next指针指向出雷区的第一个元素。但是这种方法得有一个是否进入雷区的标志，但是我觉得可以优化。

第三种方法：

优雅的递归调用

算法实现

第一种实现：

ListNode* removeElements(ListNode* head, int val) {	ListNode *pre;	ListNode *cur;	ListNode *temp;		pre = head;	while(pre != NULL && pre->val == val)	{		temp = pre;		pre = pre->next;		delete temp;	}	if(pre == NULL)	{		return NULL;	}		head = pre;	cur = pre->next;	while(cur != NULL)	{		if(cur->val == val)		{			temp = cur;			pre->next = cur->next;			delete temp;		}		else		{			pre = cur;		}		cur = cur->next;	}//while		return head;}

第二种实现：

第三种实现：

ListNode* removeElements(ListNode* head, int val) {	ListNode *temp = NULL;	if(head && head->val == val)	{		temp = head;		head = removeElements(head->next, val);		delete temp;	}	if(head && head->next)	{		head->next = removeElements(head->next, val);	}	return head;}