Creating a Union of two linked lists

[Depressed]

I am trying to create a function that unites two linked lists. I have created a function that does exactly what I am trying to do but as an array of sets instead of nodes that I will provide below.

*My Restrictions are as follows: I can use contains() and the Node class accessors and mutators, but, other than those, I cannot use any function calls in my definitions in my union function The operations must be coded without calling any other functions to help. *

Any guidance or help to get on the right track would be appreciated.

Here is my array set version of the function I am attempting to code as a linked list:

 template <class ItemType>
    ArraySet<ItemType> ArraySet <ItemType> ::setUnion(const ArraySet<ItemType> set2)
    {

        ArraySet<ItemType> unionSet;

        for (int i = 0; i < getCurrentSize(); i++)
        {
            unionSet.add(items[i]);
        }

        for (int i = 0; i < set2.getCurrentSize(); i++)
        {
            unionSet.add(set2.items[i]);
            if (items[i] == set2.items[i])
                unionSet.remove(set2.items[i]);
        }

   
        return unionSet;
    }

Here is my LinkedSet class:

#ifndef LINKED_SET_
#define LINKED_SET_

#include "SetInterface.h"
#include "Node.h"

namespace cs_set {

    template<class ItemType>
    class LinkedSet : public SetInterface<ItemType>
    {
        private:
            Node<ItemType>* headPtr;
            int itemCount;

            // Returns either a pointer to the node containing a given entry
            // or nullptr if the entry is not in the bag.
            Node<ItemType>* getPointerTo(const ItemType& target) const;
            void clone(const LinkedSet<ItemType>& copyMe);  //Copy function

        public:
            class ItemNotFoundError {};
            class DuplicateItemError {};
            LinkedSet();    //Constructor #Big3
            LinkedSet operator=(const LinkedSet<ItemType>& right);  //Assignment operator
            LinkedSet(const LinkedSet<ItemType>& aSet); //Copy Constructor #Big3
            virtual ~LinkedSet();   //Destructor #Big3
            int getCurrentSize() const;
            bool isEmpty() const;
            void add(const ItemType& newEntry);
            void remove(const ItemType& anEntry);
            void clear();
            bool contains(const ItemType& anEntry) const;
            LinkedSet<ItemType> setUnion(const LinkedSet<ItemType>* set2);
            LinkedSet<ItemType> setIntersection(const LinkedSet<ItemType>* set2);
            LinkedSet<ItemType> setDifference(const LinkedSet<ItemType>* set2);
            //int getFrequencyOf(const ItemType& anEntry) const;
            std::vector<ItemType> toVector() const;
    };
}

#include "LinkedSet.cpp"
#endif  

Node Class:

#ifndef NODE_
#define NODE_

namespace cs_set {

    template<class ItemType>
    class Node {
        private:
           ItemType item;
           Node<ItemType>* next;

        public:
           Node(const ItemType& anItem = ItemType(), Node<ItemType>* nextNodePtr = nullptr);
           void setItem(const ItemType& anItem);
           void setNext(Node<ItemType>* nextNodePtr);
           ItemType getItem() const ;
           Node<ItemType>* getNext() const ;
    };
}

#include "Node.cpp"
#endif 

SetInterface class:

#ifndef SET_INTERFACE
#define SET_INTERFACE

#include <vector>
#include <algorithm>
#include <iterator>

namespace cs_set {
    template<class ItemType>
    class SetInterface
    {
    public:
       /** Gets the current number of entries in this bag.
        @return  The integer number of entries currently in the set. */
       virtual int getCurrentSize() const = 0;

       /** Sees whether this set is empty.
        @return  True if the set is empty, or false if not. */
       virtual bool isEmpty() const = 0;

       /** Adds a new entry to this set.
        @post  If successful, newEntry is stored in the set and
           the count of items in the set has increased by 1.
        @param newEntry  The object to be added as a new entry.
        @return  True if addition was successful, or false if not. */
       virtual void add(const ItemType& newEntry) = 0;

       /** Removes one occurrence of a given entry from this set,
           if possible.
        @post  If successful, anEntry has been removed from the set
           and the count of items in the bag has decreased by 1.
        @param anEntry  The entry to be removed.
        @return  True if removal was successful, or false if not. */
       virtual void remove(const ItemType& anEntry) = 0;

       /** Removes all entries from this set.
        @post  set contains no items, and the count of items is 0. */
       virtual void clear() = 0;

       /** Counts the number of times a given entry appears in this set.
        @param anEntry  The entry to be counted.
        @return  The number of times anEntry appears in the set. */
      // virtual int getFrequencyOf(const ItemType& anEntry) const = 0;

       /** Tests whether this set contains a given entry.
        @param anEntry  The entry to locate.
        @return  True if bag contains anEntry, or false otherwise. */
       virtual bool contains(const ItemType& anEntry) const = 0;

       /** Empties and then fills a given vector with all entries that
           are in this set.
        @return  A vector containing all the entries in the bag. */
       virtual std::vector<ItemType> toVector() const = 0;

       /** Destroys this set and frees its assigned memory. (See C++ Interlude 2.) */
       virtual ~SetInterface() { }
    };
}
#endif 

[jonnin]

you may need to ask a question or explain better what you want, but from the words I see, ...
a union is everything in both sets. So list1 .tail / end/whatever .next = list2. head would do the job, with an alternate 'remove duplicates' pass after this.

if you need to preserve both lists, you need a copy of each, and at that point its just as easy to iterate both and add all the items from each into the new one, which is what you appeared to be doing.

it depends on the USE or PURPOSE of the union. You can do it by having full copies of everything, or just pointers back to the originals, or various pointer magic (you can also just have a list of lists as a third idea). How you use it depends on the most efficient way to build the final thing. Being schoolwork they *probably* want a full copy and won't accept tying them together, but you never know.

[Depressed]

@jonnin

template<class ItemType>
LinkedSet<ItemType> LinkedSet<ItemType>::setUnion(LinkedSet<ItemType> set2)
{
    Node<ItemType>* curPtr = new Node<ItemType>;

   while (curPtr->getNext() != nullptr)
   {
    curPtr = curPtr->getNext();
   }
   curPtr->setNext(headPtr);
   return *this;
}

Something like this (Note it is incomplete and only displays one set instead of a union) but, I need to preserve two sets and combine them both so set one would display like this:

Output expected:

Set 1:
one two three

Set 2:
four five six

The Union of Both sets is:

one two three four five six

As stated before, I cannot use the .add() function in my union function definition I am only limited to .contains() and the nodeclass accesors and mutators.

In the main file client it would look something like this:

    std::string items1[] = { "one", "two", "three" };
    cout << "Add 3 items to the set1: " << endl;
    for (int i = 0; i < LIMIT; i++)
    {
        try {
            set1.add(items1[i]);
            cout << items1[i] << endl;
        }
        catch (LinkedSet<string>::DuplicateItemError e)
        {
            //set.add(items[i]);
            cout << "IT IS A DUPLICATE!" << endl;
        }
    }  // end for


    cout << endl;

    std::string items2[] = { "four", "five", "six" };
    cout << "Add 3 items to the set2: " << endl;
    for (int i = 0; i < LIMIT; i++)
    {
        try {
            set2.add(items2[i]);
            cout << items2[i] << endl;
        }
        catch (LinkedSet<string>::DuplicateItemError e)
        {
            //set.add(items[i]);
            cout << "IT IS A DUPLICATE!" << endl;
        }
    }  // end for
    cout << "\nset1: " << endl;
    displaySet(set1);
    cout << "\nset2: " << endl;
    displaySet(set2);

    /*
    set3 = set1.setUnion(set2);
    cout << "The Union is: " << endl;
    displaySet(set3); */

    cout << "\nUnion is: " << endl;
    set3 = set1.setUnion(set2);
    displaySet(set3);