c++中从排序链表中删除重复值节点的方法

Question

我正在编写一个在c++中从排序链表中删除重复值节点的方法。我试图使用Node*而不是void返回类型，但由于返回语句而面临错误。

My method code..

    Node* RemoveDuplicates(Node *head)
     {
       struct Node* current = head;
       struct Node* next_next;
       if(current == NULL)
       return;
      while(current->next != NULL)
       {
         if(current->data == current->next->data)
          {
            next_next = current->next->next;
            free(current->next);
            current->next = next_next; 
          }
        else 
        {
            current = current->next;
        }
      }
  }

我收到的编译时错误信息…

   solution.cc: In function 'Node* RemoveDuplicates(Node*)':
   solution.cc:31:6: error: return-statement with no value, in function returning 'Node*' [-fpermissive]
   return ;
   ^

Answer 1

将返回类型更改为void

函数没有返回有价值的内容

Answer 2

编译器不会假装知道你在想什么，他要求你对正在发生的事情做契约。因此，声明返回类型Node*时，必须提供该特定类型的输出:Node指针。在这里，我能想到的最可能的情况是返回当前节点，而不返回函数末尾的重复节点。

Node* RemoveDuplicates(Node *head)
{
    // some instructions
    return head;
}

所以你可以有这样的语义:

Node* distinctList = RemoveDuplicates(head);
if (distinctList) // NULL (0 / false) if empty
{
    // some more instructions
}

但是，如果您不需要从函数中输出任何内容，则返回类型应该是void(无)。

希望这对你有帮助!

Answer 3

我将把这当作一个学习练习，并忽略这样一个事实:使用std列表比实现您自己的链表更好，使用new和delete比使用malloc和free更好。

如果指定Node*作为返回类型，则必须返回一个指向节点的指针。为了回答你的问题，你必须问的是:你想要返回哪个指针?如前所述，您正在删除所有重复的指针。是否要返回最后删除的指针?是否要循环直到找到重复项并将其删除?

在代码片段中有两个退出点。第一个是普通的"return"语句，当列表为空时调用它。如前所述，您正在返回void，即什么都没有。你需要返回一个指向Node的指针，但是你没有有效的指针，所以你可能想要返回一个null_ptr，这是一个不指向任何东西的指针。

现在我们来到你的问题的一部分，这取决于期望的行为。例如:

while(current->next != NULL)
   {
     if(current->data == current->next->data)
      {
        next_next = current->next->next;
        free(current->next);
        current->next = next_next; 
        ///  Here  you have a valid pointer you could return:
        return current;
      }
    else 
    {
        current = current->next;
    }
    // if you get here, no duplicates were found, so you can return a nullptr.
    return std::nullptr;
  }

将循环遍历列表，直到找到重复项，将删除该重复项，并返回指向剩余指针的指针。如果没有发现重复项，则返回nullptr。

我把它修改为循环遍历列表中的所有元素，直到找到最后一个重复的元素(提示，您必须引入一个局部变量来存储返回值)，并返回该值。

好运。