[LintCode]删除链表中的元素

原文发表在我的博客：删除链表中的元素
求关注、求交流、求意见、求建议。

问题

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 就成了一个 野指针 。