Member Avatar for heavyc

if i have a node that had a different number everytime and i want to delete only the nodes that are repeated(which has random numbers in them) and how would i count them to see how many of each i would have.

can i use if statements to count the same numbers and a if statment for the deleting ???

  • 3 Contributors
  • 6 Replies
  • 293 Views
  • 1 Day Discussion Span
  • Latest Post Latest Post by Narue

Dani AI

Generated

Short practical follow‑up that fills the gaps in the thread by , and .

Two common choices for a singly linked list:

  • Keep the first occurrence of each value and remove later duplicates (single pass, uses a hash set).
  • Remove every value that appears more than once (two passes: count, then remove nodes whose count > 1).

Both variants handle the head node and free memory when nodes are unlinked. The nested-loop method suggested by works too but is O(n^2) and is mainly useful if extra memory is not allowed.

#include <unordered_map>
#include <unordered_set>
#include <iostream>

struct Node {
    int value;
    Node* next;
    Node(int v): value(v), next(nullptr) {}
};

std::unordered_map<int,int> countOccurrences(Node* head) {
    std::unordered_map<int,int> counts;
    for (Node* cur = head; cur; cur = cur->next) ++counts[cur->value];
    return counts;
}

void removeDuplicatesKeepOne(Node*& head) {
    std::unordered_set<int> seen;
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        if (seen.find(cur->value) != seen.end()) {
            Node* toDel = cur;
            cur = cur->next;
            if (prev) prev->next = cur; else head = cur;
            delete toDel;
        } else {
            seen.insert(cur->value);
            prev = cur;
            cur = cur->next;
        }
    }
}

void removeAllDuplicates(Node*& head) {
    auto counts = countOccurrences(head);
    Node* prev = nullptr;
    Node* cur = head;
    while (cur) {
        if (counts[cur->value] > 1) {
            Node* toDel = cur;
            cur = cur->next;
            if (prev) prev->next = cur; else head = cur;
            delete toDel;
        } else {
            prev = cur;
            cur = cur->next;
        }
    }
}

Mapping to 's pseudocode: i is the current pointer (here cur), j would be the inner pointer (a runner) in the O(n^2) approach, next(i) is cur->next, and unlink(j) means reset the previous node's next (or update head if deleting the first node) then delete the node. Complexity: hash approaches are O(n) average time and O(n) extra memory; nested loops are O(n^2) time with O(1) memory. For older compilers without unordered_map/set, use std::map (O(n log n)) or the nested-loop version.

Recommended Answers

All 6 Replies

Member Avatar for Drowzee

It would be easiest to check the list beginning to end to see if you have the value already, then not make the node if there's already one with that value.

Member Avatar for Narue

Here is the basic idea behind what you're trying to do:

// Pseudocode
for ( i = first; i != last; i = next ( i ) ) {
  for ( j = next ( i ); j != last; j = next ( j ) ) {
    if ( i == j )
      unlink ( j );
  }
}

However, if your list is sorted then all you have to do is unlink one of two adjacent nodes that match.

Member Avatar for heavyc

Here is the basic idea behind what you're trying to do:

// Pseudocode
for ( i = first; i != last; i = next ( i ) ) {
  for ( j = next ( i ); j != last; j = next ( j ) ) {
    if ( i == j )
      unlink ( j );
  }
}

However, if your list is sorted then all you have to do is unlink one of two adjacent nodes that match.

but lets say that there is 10 numbers and they are random everytime would this still work or would i have to do something else.

Member Avatar for Narue

>but lets say that there is 10 numbers and they are random everytime
You can say that, but you've already said it and I understood you completely the first time.

>would this still work
Yes, what I gave you was an inefficient algorithm that assumes nothing about the input sequence. So it will work with random numbers that potentially have duplicates. But you would have known that if you bothered to work through a sample sequence instead of coming back here to ask us without first thinking for yourself.

Member Avatar for heavyc

>but lets say that there is 10 numbers and they are random everytime
You can say that, but you've already said it and I understood you completely the first time.

>would this still work
Yes, what I gave you was an inefficient algorithm that assumes nothing about the input sequence. So it will work with random numbers that potentially have duplicates. But you would have known that if you bothered to work through a sample sequence instead of coming back here to ask us without first thinking for yourself.

yes i understand what u mean about tryng it buut i did and i dont know what to plugg into those variables that you did .. if you could please help

Member Avatar for Narue

I already gave you code for a linked list that gives you more than enough information to translate the pseudocode into valid C++. You won't learn anything if I just do it for you.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.