题目说明: 删除链表中等于给定值 val 的所有节点
示例:
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
首先我们需要清除链表的概念(链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。)其结构图如下:
思路:
运用双指针解法,如下图所示,定义prev = NULL;cur= head;
根据cur->val是否等于给定val
进行判断。
需要注意一个特殊情况:
当head -> val == val
即输入: 6->2->6->3->4->5->6, val = 6
时。此时需要一个新的 head,令head = cur -> next; cur = head;
程序实现如下:
struct ListNode* removeElements(struct ListNode* head, int val)
{
struct ListNode* prev = NULL;
struct ListNode* cur = head;
while(cur)
{
if(cur->val != val)
{
prev = cur;
cur = cur->next;
}
else
{
if(cur == head)
{
head = cur->next;
free(cur);
cur = head;
}
else
{
prev->next = cur->next;
free(cur);
cur = prev->next;
}
}
}
return head;
}