删除链表中的元素

  |   分类   |   热度 ℃

前言

LintCode 是专注代码面试的在线评测系统，有很多代码题，可以用 Java、C++、Python 在线答题，我觉得还不错，就决定把做一做这些题，然后把题目的实现、优化思路写下来，一来是为了有更深的理解，二来是讨论一下还有没有更好的方法。

问题

LintCode：删除链表中的元素

描述

删除链表中等于给定值 val 的所有节点。

样例

给出链表 1->2->3->3->4->5->3 和 val = 3，你需要返回删除 3 之后的链表： 1->2->4->5 。

链表的数据结构

1
2
3
4
5
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

实现 - C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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 就成了一个 野指针 。

本文链接：删除链表中的元素
版权声明：本文章采用CC BY-NC-SA 3.0 CN许可协议进行许可。转载请注明出处！