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

效果如下：