Question

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 去值为val的元素

Algorithm

法一：用两个指针，一个遍历，一个作为前驱结点 法二：用一个指针就可以

Accepted Code：

法一：（效率不高）

class Solution { public: ListNode* removeElements(ListNode* head, int val) { if(head==NULL) return head; ListNode* preHead=new ListNode(-1); preHead->next=head; ListNode* p=head; ListNode* ppre=preHead; while(p!=NULL) { if(p->val==val) { ppre->next=p->next; } else { ppre=ppre->next; } p=p->next; } return preHead->next; } };

法二：

class Solution { public: ListNode* removeElements(ListNode* head, int val) { if(head==NULL) return NULL; ListNode* p=head; while(p!=NULL && p->val==val) //考虑头结点的值等于val的情况 p=p->next; head=p; while(p!=NULL && p->next!=NULL) { if(p->next->val==val) p->next=p->next->next; else p=p->next; } return head; } };