题目描述
删除链表中等于给定值 val 的所有节点。
样例
输入: 1->2->6->3->4->5->6, val = 6
输出: 1->2->3->4->5
解法1:在原链表修改:
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *p=head;//当前判断元素
ListNode *k=p;//指向前一个元素
while(p)
{
if(p->val==val)
{
if(p==head)//头元素要删的情况
{
head=p->next;
p=head;
if(head==NULL)
return head;
else continue;
}
else if(p->next==NULL)//末尾元素要删的情况
{
k->next=NULL;
return head;
}
else//中间元素
{
k->next=p->next;
p=k->next;
continue;
}
}
k=p;
p=p->next;
}
return head;
}
};
解法2:将不需要删除的元素添加到新链表
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
ListNode *L=new ListNode(-1);
ListNode *l1=L;
while(head)
{
if(head->val==val)
head=head->next;
else
{
ListNode *p=new ListNode(head->val);
l1->next=p;
l1=l1->next;
head=head->next;
}
}
return L->next;
}
};
解法3:递归实现
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (!head)
return head;
head->next = removeElements(head->next, val);
return head->val == val ? head->next : head;
}
};