数据结构 - 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

There are a few questions here that I don’t understand very clearly. Please check them carefully

1. head is defined at the beginning, but a NULL check is performed without assigning a value. Although head is not assigned a value, it is a random address and will not be NULL, but there is still a clear logical error here

2. first From the meaning of the word, it represents the first node, but you used it to represent the previous node. Is it easier to understand if it is renamed last? In the same way, it is recommended that the current pointer p be renamed current.

3. In the if condition, it seems that there is no need to define a del to point to p, because p->next is used later. After changing the connection, just delete p can be used, and then p = head Or p = first->next to change the current pointer.

4. Delsame is defined as bool, but the returned value is head

No problems have been found in other logic for the time being. I think we can analyze and deal with the above problems first and then see the effect.

Give you a JavaScript algorithm reference

JavaScript mainly provides algorithm ideas, and those who have studied C/C++ should understand it. Then you can think about how to implement it in C++ based on this idea.

Note:

1. JavaScript refers to objects. This reference is similar to a C++ pointer and is different from a C++ reference

2. JavaScript does not require delete, so you need to add delete in the appropriate place after changing it to a C++ program.

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();

One reason why I don’t write C++ code is to let you use your brain, and the other reason is that I am too lazy to configure the environment

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;
        }
    }

Note that this is an interval that is closed on the left and open on the right, that is: data within the range of [first, last);
Usage example: li.Remove(3)
where: begin and end are as follows:

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

The effect is as follows: