数据结构 - C++单链表删除指定元素的问题？

Question

template <class T>
bool SingleList<T>::Delsame(T x)
{
    Node<T> *head;
    if(NULL == head) return head;
    Node<T> *p=head;
    Node<T> *first=NULL;
    while(NULL != p){
        if(p->element == x){
            Node<T> *del =p;
            p=p->link;
            if(NULL!= first){
                first->link=p;
            }else{
                head=p;
            }
            delete del;
        } else{
            first=p;
            p=p->link;
        }
    }
    return head;
}

代码如上，如 1 2 3 2 4 5 2
需要删除所有的2，
希望得到的结果是1 3 4 5
但目前得到的是1 2 3 4 5，
以及存在无法删除只有一个的元素、连续相同元素无法删除的问题，
如何修改可以将所有相同元素都删去呢？

Answer 1

这里有几个问题我看得不是很明白，请你仔细检查一下

1. head 一开始就定义了，但没赋值就进行了 NULL 检查。虽然没赋值 head 是个随机地址不会为 NULL，但这里还是一个很明确的逻辑错误

2. first 从词意上来看，表示第一个节点，但你是用来表示上一个节点的，这里改名为 last 比较容易理解？同理，当前指针 p 建议改名为 current。

3. 在 if 条件中，似乎不需要定义一个 del 来指向 p，因为后面都在使用 p->next，把连接改了之后直接 delete p 就可以了，然后可以 p = head 或者 p = first->next 来改变当前指针。

4. Delsame 定义为 bool，但是返回的却是 head

其它逻辑暂时没发现啥问题，我觉得可以先把上面的问题分析处理了再来看看效果。

给你个 JavaScript 的算法参考

JavaScript 主要是提供算法思路，学过 C/C++ 的应该看得明白。然后你可以按这个思路来思考 C++ 怎么实现。

注意：

1. JavaScript 对对象是引用，这个引用类似 C++ 的指针，与 C++ 的引用不同

2. JavaScript 不需要 delete，所以改成成 C++ 程序之后需要在合适的地方添加 delete。

class SingleList {
    constructor() {
        this.head = null;
        this.tail = null;
    }

    print(tag) {
        let current = this.head;
        function* iterate() {
            while (current) {
                yield current.value;
                current = current.next;
            }
        }
        console.log(`${tag}: ${Array.from(iterate())}`);
    }

    add(...args) {
        let current = this.findTail();
        args.forEach(v => {
            if (current) {
                current.next = {
                    value: v
                };
                current = current.next;
            } else {
                this.head = current = {
                    value: v
                };
            }
        });
    }

    findTail() {
        if (!this.head) {
            return null;
        }

        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        return current;
    }

    remove(v) {
        let current = this.head;
        let last = null;
        while (current) {
            if (current.value === v) {
                if (last) {
                    last.next = current.next;
                } else {
                    this.head = current.next;
                }
                current = current.next;
            } else {
                last = current;
                current = current.next;
            }
        }
    }
}

function main() {
    const list = new SingleList();
    list.add(1, 2, 3, 2, 4, 5, 2);
    list.print("原始值");
    list.remove(2);
    list.print("删除 2");
    list.add(2, 3, 1, 3, 1);
    list.print("新增值");
    list.remove(1);
    list.print("删除 1");
}

main();

不写 C++ 代码一个是为了让你动动脑筋，二个是因为我懒得去配环境

Answer 2

    void Remove(T t)
    {
        Node<T>* p = head;
        Node<T>* first = begin();
        Node<T>* last = end();
        while (first != last) {
            if ((*first).data == t) {
                Node<T>* tmp = first;
                p->next = first->next;
                delete tmp;
                first = p;
            }
            p = first;
            first = first->next;
        }
    }

注意，这是一个左闭右开的区间，即：[first, last)范围内的数据；
用法例子：li.Remove(3)
其中：begin 和 end 如下:

Node<T>* begin() { return head->next; } // 注意：此代码中始终有个 head 头（不为空），head 指向真正的链表数据
Node<T>* end() { return nullptr; }

效果如下：