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

2022-01-01 00:00:00 linked-list c++
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

在此处输入图片描述

我正在编写一个函数,如果两个值相同,它将删除链表中连续的两个值.当输入类似于1 -> 2 -> 3 -> 3 -> 4 -> nullptr"时,我的代码似乎停止工作.(输出应为 1 -> 2 -> 4 -> nullptr).它退出而不给我任何错误.我一行一行地调试,它突然退出并显示变量不可用".

Hi, I am writing a function that would delete two values in a row in a linked list if the two values are the same. My code seems to stop working when the input is something like "1 -> 2 -> 3 -> 3 -> 4 -> nullptr".(the output should be 1 -> 2 -> 4 -> nullptr). It exits without giving me any error. And I went through the debug line by line, It just suddenly exits and showed "variables are not available".

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

I am guessing it is the problem that when I delete p, the l points to garbage, which causes the problem. So I tried a different way to make l point to to_delete -> next. But it still does not work.

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

I have tried so many hours to fix it and the debug won't even help. Can someone please help? Thank you so much!

推荐答案

我已经简化了上面的代码,你上面的逻辑也不会帮助你删除多个重复项.那么让我们看看下面的代码并剖析它:

I have simplified the code above, the logic you have above also wont help you remove multiple duplicates. So lets look at the code below and dissect it:

   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,这是列表的实际开始.

There seems to be a need for a dummy node at the start because if we have 1 -> 1 - > 2 we need to delete the first two and point to the correct head which is a 2. In order to avoid this confusion is better to keep a dummy node at the start and at the end just set the output of your list to be p = dummy.next, which is the actual start of your list.

我定义了一些临时变量,tempduplicate,temp 帮助我在列表中进一步导航并复制以保存重复值,将指针移到下一个和删除节点.prev 是指向重复项之前节点的前一个指针.

I have defined some temporaries, temp and duplicate, temp to help me navigate further in the list and duplicate to hold the duplicate value, move the pointer to next and delete the node. prev is the previous pointer to the node just before the duplicates.

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

Each node in the list, temp = p I move forward until looking for the adjacent match p->value == temp->next->value if there is a match I delete the current node and the one I found ahead of it. I use the prev tracker to restore the order of the list by correctly setting its next, else I break from my inner loop and move on to the next value, the outer loop p = p->next.

我不确定你的 LN<T> 结构,所以我继续我的想法.

I am not sure about your LN<T> struct so I have gone ahead with what I think it is.

演示链接

相关文章