正确实现单链表 C++

2022-01-01 00:00:00 linked-list c++

我有一份雇主名单，例如:

I have a list with names of employers such as:

节点 1:吉尔、马特、乔、鲍勃、马特

Node 1: Jill, Matt, Joe, Bob, Matt

节点 2:杰夫、詹姆斯、约翰、乔纳森、约翰、爱德华

Node 2: Jeff, James, John, Jonathan, John, Edward

节点 3:Matt、Doe、Ron、Pablo、Ron、Chase、Ron、Chase、路易

Node 3: Matt, Doe, Ron, Pablo, Ron, Chase, Ron, Chase, Loui

并且我正在尝试将它放到哪里，如果它看到重复，它会将其发送到列表的前面并删除该当前节点，使其看起来像这样

and I'm trying to get it to where if it sees a repeat it will send it to the front of the list and delete that current node, so that it will look like this

节点 1:马特、吉尔、乔、鲍勃

Node 1: Matt, Jill, Joe, Bob

节点 2:约翰、杰夫、詹姆斯、乔纳森、爱德华

Node 2: John, Jeff, James, Jonathan, Edward

节点 3:Chase、Ron、Matt、Doe、Pablo、Loui

Node 3: Chase, Ron, Matt, Doe, Pablo, Loui

不幸的是，我的输出接近我想要的.它正在删除重复的条目，但它没有发送到前面..

Unfortunately, My output is close to what I would like. It's deleting the duplicate entries, but it's not sending to the front. .

我的输出:

节点 1:吉尔、马特、乔、鲍勃

Node 1: Jill, Matt, Joe, Bob,

推荐答案

好吧，让我们看看:

当你点击 if (ptr->data == p->data) 时:

  • pp 指向列表末尾
  • p 是你的新节点(没有指向它，也没有指向它)
  • ptr 指向有重复数据的节点
  • pp points to the end of the list
  • p is you new node (nothing points to it and it points to nothing)
  • ptr points to the node with duplicate data

为了删除节点，你实际上需要让 next 指针指向 ptr 否则你怎么能从中删除 ptr列表?所以你实际上需要检查:

In order to delete the node you need to actually need to have the next pointer pointing to ptr otherwise how can you remove ptr from the list? So you would actually need to check:

if (head && head->data == p->data)
{
    // do nothing as duplicate entry is already head of list
    delete p;
    return;
}

node *ptr = head;
while (ptr)
{
    if (ptr->next && ptr->next->data == p->data)
    {
        node *duplicate = ptr->next;
        ptr->next = duplicate->next; // skip the duplicate node
        duplicate->next = head;      // duplicate points to head
        head = duplicate;            // head is now the duplicate
        delete p;                    // otherwise leaking memory
        return;
    }
    ptr = ptr->next;
}

if (pp) // points to tail as per your code
{
    pp->next = p;
    ++N;
}

相关文章