原文发表在我的博客：删除链表中的元素
求关注、求交流、求意见、求建议。
问题
LintCode：删除链表中的元素
描述
删除链表中等于给定值 val 的所有节点。
样例
给出链表 1->2->3->3->4->5->3 和 val = 3，你需要返回删除 3 之后的链表： 1->2->4->5 。
链表的数据结构
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
实现 - C++
class Solution {
public:
ListNode *removeElements(ListNode *head, int val) {
// 21ms
ListNode *prev = NULL;
ListNode *p = head;
ListNode *buffer;
while (p != NULL) {
if (p->val == val) {
if (prev != NULL)
prev->next = p->next;
else
head = p->next;
buffer = p;
p = p->next;
delete buffer;
} else {
prev = p;
p = p->next;
}
}
return head;
}
};
总结
简单题不需要太多分析，注意几个细节就可以：
- 返回时要返回头指针，所以要使用另一个指针遍历。
- 删除节点不能只是跳过，一定 要用
delete释放内存。 - 删除头节点时，头指针会改变，返回值 一定 要改成新的头指针。
- 删除尾节点时，必须 将前一个节点的
next置为NULL。如果只是将尾节点delete并置为NULL，那么前一个节点的next就成了一个野指针。
