I'm trying to remove duplicates from a sorted linked list. I have written the algorithm but still missing a core bug logic that I can't trace.

Consider the list 1->2->3->3->4->4->5

Output should be 1 - > 2 - > 5 The program works fine for a simple case, like 1>2>2>3, but for multiple duplicates like 1>2>2>3>3>5 it outputs 1>3>5 Here is a complete program:

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;
        }
    }


}

CodePudding user response：

For starters this constructor

Node()
{

}

does not make a sense. Remove it.

The statement

prevSlow->next = fast->next;

in this if statement

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

in general can invoke undefined behavior because initially the pointer prevSlow is set to nullptr

Node* prevSlow = nullptr;

Pay attention to that the node n1 is the head node of the list. It can be changed in the process of removing duplicates. Also you need to free memory of removed nodes.

The algorithm can be implemented the following way

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;
    }
}