leetcode：Remove Linked List Elements

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

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

Credits:
Special thanks to @mithmatt for adding this problem and creating all test cases.

分析：题意就是删除链表中指定的值。

一开始以为很简单，不就是链表中删除元素嘛，于是：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if(head==NULL) return NULL;
ListNode *result = head;
while(head){
if(head->val==val){
if(head->next==NULL){
ListNode *temp = head;
head = head->next;
delete temp;
return head;
}
else{
ListNode* temp=head->next;
head->next=temp->next;
delete temp;
}
}
head=head->next;
}
return result;
}
};

显示出错：

Input:[1,1], 1

Output:[1]

Expected:[]

仔细审视代码发现自己确实疏漏了链表中连续两个都是制定删除元素的情况，而且这个逻辑是不正确的：每次删除操作时，都会执行head->next=head->next->next，而之后进行遍历下一个元素时head=head->next会跳过一个元素了，所以出错。

为了解决这个问题：

/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeElements(ListNode* head, int val) {
if (head == NULL)
{
return NULL;
} ListNode *result = head;
ListNode *p = head;
while (p && p->val == val)
{
ListNode *temp = p;
p = p->next;
delete temp;
}
result = p; //新的头指针 while (p)
{
if (p->next && p->next->val == val)
{
ListNode *temp = p->next;
p->next = p->next->next;
delete temp;
continue;
}
p = p->next;
} return result;
}
};

或者：可参考方案，1、采用两个指针p和q，p指向当前合法的元素，q指向下个可能合法的元素，合法的判断在于是否为空。

2、通过q指针遍历链表，如果当前元素合法，则p和q都向后移动，如果当前元素不合法，则p->next=q->next，跳过这个不合法的元素。注意只有在元素合法的时候才移动p。

#include<cstdio>
using namespace std;struct ListNode{
int val;
ListNode *next;
ListNode(int x): val(x), next(NULL){ }
};
ListNode* removeElements(ListNode *head, int val){
//p指向list中第一个合法的元素
ListNode *p = head;
while(p && p->val == val){
p = p->next;
}
if(p == NULL){
return NULL;
}
ListNode *q = p->next;
head = p; //新的head指针
//用q去遍历整个list
while(q != NULL){
if(q->val == val){
//q指向的元素要被删除
p->next = q->next;
q = q->next; //q继续向前移动
}
else { //找到了一个合法元素
p = p->next;
q = q->next;
}
}
return head;
}
int main(){
ListNode *p = new ListNode(1);
ListNode *q = new ListNode(2);
p->next = q;
ListNode *head = removeElements(p, 1);
printf("%d", head&&head->val);
return 1;
} </cstdio>