Right now my code is a little... over-complicated. I feel I must be missing a simpler algorithm for getting this task done. Basically the only rules for this assignment are that we can't use containers or other libraries. I'll include my code below so you might get a better idea what I'm trying to do. The code compiles, but only gives me correct output sometimes.

The code has a few steps, it first iterates through a linked list which can have any data type and extracts one element at a time. Then it will compare each element against every other element in the list, if 2 matches are found among all the data in the list then the 2nd matching element is removed and the number of matches is set back to 1.

I'm performing a push_back() and pop_front() on every element, but only a pop_front() on data which is repeated (when numMatches = 2).

At the end, I reorganize based on the number of deletions done (or the number of extra elements) to put the list back in order.

I'm not quite sure where the error is popping up, I feel it must have to do with the method of push_back() and pop_front() but I can't think of another way to iterate through pointers without the option of element access.

As an example i/o if {1, 2, 4, 2, 3, 2, 3} was the input, the output would be {1, 2, 4, 3}

void unique(){
    if (this->size_ <= 0){
      throw std::domain_error("unique() : must be 1 or more elements");
    }
    // check each value against every other value
    // nested for loops?
    // always push, pop for any matches
    Node* outerElem = this->head_;
    int numDeletions;
    for (unsigned i = 0; i < this->size_;   i){
      int numMatches = 0;
      auto cmp = outerElem->data;
      Node* innerElem = this->head_;
      for(unsigned j = 0; j < this->size_   1;   j) {
        if (innerElem->data == cmp){
            numMatches;
        }
        if (numMatches <= 1) {
          // not delete, means we found same element
          // or non-matching element
          push_back(innerElem->data);
          innerElem = innerElem->next; 
          pop_front();
        } else if (numMatches == 2) {
          // means there are at least 2 instances of the same element
          innerElem = innerElem->next;
          pop_front();
            numDeletions;
          --numMatches; // reset numMatches so it can detect if there's another match
        }
      }
    }
    for(unsigned k = 0; k < numDeletions;   k) { // put values in original order
      push_back(this->head_->data);
      pop_front();
    }
  }

Here is the code for the Node class, which contains the pointers used:

 struct Node {
    T data;  // Actual value for list element
    Node* next = nullptr;
    Node* prev = nullptr;
  };
  Node* head_ = nullptr;
  Node* tail_ = nullptr;
  std::size_t size_ = 0;
};

CodePudding user response：

I would suggest providing a remove method on your linked list, and then you can just remove any found duplicates in your nested loop:

    void removeNode(Node* node) {
        // This method assumes that the provided node is a member of the list
        if (node == head_) {
            head_ = head_->next;
        } else {
            node->prev->next = node->next;
        }
        if (node == tail_) {
            tail_ = tail_->prev;
        } else {
            node->next->prev = node->prev;
        }
        size_--;
        delete node;
    }

    void unique() {
        Node* outerElem = this->head_;
        while (outerElem != nullptr) {
            auto cmp = outerElem->data;
            Node* innerElem = outerElem;
            while (innerElem->next != nullptr) {
                if (innerElem->next->data == cmp) {
                    removeNode(innerElem->next);
                } else {
                    innerElem = innerElem->next;
                }
            }
            outerElem = outerElem->next;
        }
    }