修复了从排序的链表中删除重复项的错误

Question

我正在尝试从排序的链表中删除重复项。我已经编写了算法，但仍然缺少一个我无法跟踪的核心错误逻辑。

考虑一下这个列表1->2->3->3->4->4->5

输出应为1->2->5.该程序适用于简单的情况，如1>2>2>3，但是对于像1>2>2>3>3>5，它输出1>3>5.这是一个完整的程序：

struct Node
{
    Node* next;
    int val;
    Node()
    {
    }
};
int main()
{
    Node* n1 = new Node();
    n1->val = 1;
    Node* n2 = new Node();
    n2->val = 2;
    n1->next = n2;
    Node* n3 = new Node();
    n3->val = 3;
    n2->next = n3;
    Node* n4 = new Node();
    n4->val = 3;
    n3->next = n4;
    Node* n5 = new Node();
    n5->val = 4;
    n4->next = n5;
    Node* n6 = new Node();
    n6->val = 4;
    n5->next = n6;
    Node* n7 = new Node();
    n7->val = 5;
    n6->next = n7;
    n7->next = nullptr;
    Node* fast = n1->next;
    Node* slow = n1;
    Node* temp = n1;
    Node* prevSlow = nullptr;
    while (slow != nullptr && fast != nullptr)
    {
        if (fast->val == slow->val)
        {
            prevSlow->next = fast->next;
            fast = fast->next;
            slow->next = prevSlow->next;
        }
        else {
            prevSlow = slow;
            slow = slow->next;
            fast = fast->next;
        }
    }

}

Answer 1

对于初学者来说，这个构造函数

Node()
{
}

没有道理。移除它。

声明

prevSlow->next = fast->next;

在这个if语句中

if (fast->val == slow->val)
{
    prevSlow->next = fast->next;
    fast = fast->next;
    slow->next = prevSlow->next;
}

通常可以调用未定义的行为，因为最初指针prevSlow被设置为nullptr

Node* prevSlow = nullptr;

请注意，节点n1是列表的头节点。它可以在删除重复项的过程中更改。此外，您还需要释放已删除节点的内存。

该算法可以通过以下方式实现

auto is_duplicate = [] ( const Node *node )
{
    return node->next != nullptr && node->val == node->next->val;
};
for ( Node **current = &n1; *current != nullptr; )
{
    if ( is_duplicate( *current ) )
    {
        do
        {
            Node *tmp = *current;
            *current = ( *current )->next;
            delete tmp;
        } while ( is_duplicate( *current ) );
        Node *tmp = *current;
        *current = ( *current )->next;
        delete tmp;
    }
    else
    {
        current = &( *current )->next;
    }
}