c++ - 如何删除链表中连续的两项

Question

void delete_double (LN<T>*& l) {
    if (l == nullptr)
        return;

    LN<T> *p = l;
    while ( p -> next != nullptr && p -> next -> next != nullptr)
    {
        if (p -> value == p -> next -> value) // the current value is equal to the next value in the linked list 
        {
            if (p == l)                     // when the first two values are the same                                        // not sure if it is correct
            {
                l = l -> next -> next;
            }
            else                            // Problem should be here
            {
                LN<T> *to_delete = p;       //  Also tried this (doesn't work)
                p = p->next;
                delete to_delete;           //  LN<T>* to_delete = p;
                                            //  LN<T>* to_delete2 = p -> next;
                LN<T> *to_delete1 = p;      //  l = to_delete2 -> next;
                p = p->next;                //  delete to_delete;
                delete to_delete1;          //  delete to_delete2;
            }
        }
        else
        {
            p = p-> next;
        }
    }
}
//  Image below is my output

enter image description here

您好，我正在编写一个函数，如果两个值相同，它将删除链表中一行中的两个值。当输入类似于“1 -> 2 -> 3 -> 3 -> 4 -> nullptr”时，我的代码似乎停止工作。(输出应该是 1 -> 2 -> 4 -> nullptr)。它退出时没有给我任何错误。我逐行调试，它突然退出并显示“变量不可用”。

我猜测问题是当我删除 p 时，l 指向垃圾，这导致了问题。所以我尝试了一种不同的方式让 l 指向 to_delete -> next。但是还是不行。

我已经尝试了很多小时来修复它，但调试甚至都无济于事。有人可以帮忙吗？太感谢了!

Answer 1

我已经简化了上面的代码，您上面的逻辑也不会帮助您删除多个重复项。因此，让我们看看下面的代码并对其进行剖析:

   void delete_double(LN<T>*& l) {

        if (l == nullptr)
            return;

        LN<T> *p = l;
        LN<T> dummy(0);
        dummy.next = l;
        p = &dummy;

        LN<T> *temp;
        LN<T> *duplicate;
        LN<T> *prev;

        while (p != nullptr && p->next != nullptr)
        {
            temp = p;
            while (p != nullptr && temp->next != nullptr)
            {
                if (p->value == temp->next->value)
                {
                    duplicate = temp->next;
                    temp->next = temp->next->next;
                    delete duplicate;

                    duplicate = p;
                    prev->next = p->next;
                    p = prev;
                    delete duplicate;

                    temp = p;
                }
                else
                {
                    break;
                }
            }
            prev = p;
            p = p->next;
        }

        l = dummy.next;
    }

开始时似乎需要一个虚拟节点，因为如果我们有 1 -> 1 -> 2，我们需要删除前两个并指向正确的头，即 2。为了避免这种情况混淆最好在开头保留一个虚拟节点，最后只需将列表的输出设置为 p = dummy.next，这是列表的实际开始。

我已经定义了一些临时对象，temp和 duplicate , temp 帮助我在列表中进一步导航并复制以保存重复值，将指针移动到下一个并删除节点。 prev是指向重复之前节点的前一个指针。

列表中的每个节点，temp = p我继续前进，直到找到相邻的比赛 p->value == temp->next->value如果匹配，我删除当前节点和我在它之前找到的节点。我用 prev跟踪器通过正确设置其 next 来恢复列表的顺序, 否则我会从我的内部循环中断并继续下一个值，即外部循环 p = p->next .

我不确定你的 LN<T> struct 所以我按照我的想法继续前进。

Demo Link