C++ Split a LinkedList into 2 and destroy input List
<p>From a C++ beginner. I wrote a method (below) that splits the input list into 2 other lists and leave original unchanged (it works), I need a new method  "split" that destroys the input chain ∗this and uses its nodes to construct the chains a and b.  my attempts to delete the original chain has been unsuccessful. Thanks in advance.</p>

<pre><code>// Split A into two chains B and C.
// When done, A is unchanged.
template &lt;class T&gt;
void chain&lt;T&gt;split(chain&lt;T&gt;&amp; A, chain&lt;T&gt;&amp; B, chain&lt;T&gt;&amp; C)
{
    // first free all nodes in B and C

    int j;
    j=0 ;
    listSize = B.listSize;
    for (j=0 ; j &lt; listSize; j++)
        B.erase(0);

    // C.Erase();
    j=0 ;
    listSize = C.listSize;
    for (j=0 ; j &lt; listSize; j++)
        C.erase(0);


    // assign elements alternately to B and C
    int n=0;
    chain&lt;T&gt;::iterator a = A.begin(); // find first node of A
    while (a != A.end()) {
        // first give B an element
        B.insert(n,*a);
        a++;

        if (a == A.end()) break;
        // now give C an element
        C.insert(n,*a);
        a++;
        n=n+1;
    }
}

    #ifndef chain_
    #define chain_
    #include "linearList.h"
    #include "chainNode.h"

    using namespace std;
    template&lt;class T&gt;

    class linkedDigraph;
    template &lt;class T&gt; class linkedWDigraph;

    template&lt;class T&gt;
    class chain : public linearList&lt;T&gt; 
    {
       friend linkedDigraph;
       friend linkedWDigraph&lt;int&gt;;
       friend linkedWDigraph&lt;float&gt;;
       friend linkedWDigraph&lt;double&gt;;


       public:
          // constructor, copy constructor and destructor
          chain(int initialCapacity = 10);
          chain(const chain&lt;T&gt;&amp;);
          ~chain();

          // ADT methods
          bool empty() const {return listSize == 0;}
          int size() const {return listSize;}
          T&amp; get(int theIndex) const;
          int indexOf(const T&amp; theElement) const;
          void erase(int theIndex);
        void Split(chain&lt;T&gt;&amp; A, chain&lt;T&gt;&amp; B, chain&lt;T&gt;&amp; C);

              //Operator []
          typedef int size_type;



            // iterators to start and end of list
          class iterator;
          iterator begin() {return iterator(firstNode);}
          iterator end() {return iterator(NULL);}

          // iterator for chain
          class iterator 
          {
             public:
                // typedefs required by C++ for a forward iterator
                typedef forward_iterator_tag iterator_category;
                typedef T value_type;
                typedef ptrdiff_t difference_type;
                typedef T* pointer;
                typedef T&amp; reference;

                // constructor
                iterator(chainNode&lt;T&gt;* theNode = NULL)
                   {node = theNode;}

                // dereferencing operators
                T&amp; operator*() const {return node-&gt;element;}
                T* operator-&gt;() const {return &amp;node-&gt;element;}

                // increment
                iterator&amp; operator++()   // preincrement
                         {node = node-&gt;next; return *this;}
                iterator operator++(int) // postincrement
                          {iterator old = *this;
                           node = node-&gt;next;
                           return old;
                          }


                // equality testing
                bool operator!=(const iterator right) const
                      {return node != right.node;}
                bool operator==(const iterator right) const
                      {return node == right.node;}
             protected:
                chainNode&lt;T&gt;* node;

          };  // end of iterator class


       //Overload []
         T&amp; operator[](size_type index) 
            { 

                return element[index]; 
            }

       const T&amp; operator[](size_type index) const
            {

                return element[index];
            }


       protected:
          void checkIndex(int theIndex) const;
                // throw illegalIndex if theIndex invalid
          chainNode&lt;T&gt;* firstNode;  // pointer to first node in chain
          int listSize;             // number of elements in list
    };

    template&lt;class T&gt;
    chain&lt;T&gt;::chain(int initialCapacity)
    {// Constructor.
       if (initialCapacity &lt; 1)
       {ostringstream s;
        s &lt;&lt; "Initial capacity = " &lt;&lt; initialCapacity &lt;&lt; " Must be &gt; 0";
        throw illegalParameterValue(s.str());
       }
       firstNode = NULL;
       listSize = 0;
    }

    template&lt;class T&gt;
    chain&lt;T&gt;::chain(const chain&lt;T&gt;&amp; theList)
    {// Copy constructor.
       listSize = theList.listSize;

       if (listSize == 0)
       {// theList is empty
          firstNode = NULL;
          return;
       }

       // non-empty list
       chainNode&lt;T&gt;* sourceNode = theList.firstNode;
                        // node in theList to copy from
       firstNode = new chainNode&lt;T&gt;(sourceNode-&gt;element);
                        // copy first element of theList
       sourceNode = sourceNode-&gt;next;
       chainNode&lt;T&gt;* targetNode = firstNode;
                        // current last node in *this
       while (sourceNode != NULL)
       {// copy remaining elements
          targetNode-&gt;next = new chainNode&lt;T&gt;(sourceNode-&gt;element);
          targetNode = targetNode-&gt;next;
          sourceNode = sourceNode-&gt;next;
       }
       targetNode-&gt;next = NULL; // end the chain
    }

    template&lt;class T&gt;
    chain&lt;T&gt;::~chain()
    {// Chain destructor. Delete all nodes in chain.
       while (firstNode != NULL)
       {// delete firstNode
          chainNode&lt;T&gt;* nextNode = firstNode-&gt;next;
          delete firstNode;
          firstNode = nextNode;
       }
    }

    template&lt;class T&gt;
    void chain&lt;T&gt;::checkIndex(int theIndex) const
    {// Verify that theIndex is between 0 and listSize - 1.
       if (theIndex &lt; 0 || theIndex &gt;= listSize)
       {ostringstream s;
        s &lt;&lt; "index = " &lt;&lt; theIndex &lt;&lt; " size = " &lt;&lt; listSize;
        throw illegalIndex(s.str());
       }

    }

    template&lt;class T&gt;
    T&amp; chain&lt;T&gt;::get(int theIndex) const
    {// Return element whose index is theIndex.
     // Throw illegalIndex exception if no such element.
       checkIndex(theIndex);

       // move to desired node
       chainNode&lt;T&gt;* currentNode = firstNode;
       for (int i = 0; i &lt; theIndex; i++)
          currentNode = currentNode-&gt;next;

       return currentNode-&gt;element;
    }

    template&lt;class T&gt;
    int chain&lt;T&gt;::indexOf(const T&amp; theElement) const
    {// Return index of first occurrence of theElement.
     // Return -1 if theElement not in list.

       // search the chain for theElement
       chainNode&lt;T&gt;* currentNode = firstNode;
       int index = 0;  // index of currentNode
       while (currentNode != NULL &amp;&amp; 
              currentNode-&gt;element != theElement)
       {
          // move to next node
          currentNode = currentNode-&gt;next;
          index++;
       }

       // make sure we found matching element
       if (currentNode == NULL)
          return -1;
       else
          return index;
    }

    template&lt;class T&gt;
    void chain&lt;T&gt;::erase(int theIndex)
    {// Delete the element whose index is theIndex.
     // Throw illegalIndex exception if no such element.
       checkIndex(theIndex);

       // valid index, locate node with element to delete
       chainNode&lt;T&gt;* deleteNode;
       if (theIndex == 0)
       {// remove first node from chain
          deleteNode = firstNode;
          firstNode = firstNode-&gt;next;
       }
       else 
       {  // use p to get to predecessor of desired node
          chainNode&lt;T&gt;* p = firstNode;
          for (int i = 0; i &lt; theIndex - 1; i++)
             p = p-&gt;next;

          deleteNode = p-&gt;next;
          p-&gt;next = p-&gt;next-&gt;next; // remove deleteNode from chain
       }
       listSize--;
       delete deleteNode;
    }

    template&lt;class T&gt;
    void chain&lt;T&gt;::insert(int theIndex, const T&amp; theElement)
    {// Insert theElement so that its index is theIndex.
       if (theIndex &lt; 0 || theIndex &gt; listSize)
       {// invalid index
          ostringstream s;
          s &lt;&lt; "index = " &lt;&lt; theIndex &lt;&lt; " size = " &lt;&lt; listSize;
          throw illegalIndex(s.str());
       }

       if (theIndex == 0)
          // insert at front
          firstNode = new chainNode&lt;T&gt;(theElement, firstNode);
       else
       {  // find predecessor of new element
          chainNode&lt;T&gt;* p = firstNode;
          for (int i = 0; i &lt; theIndex - 1; i++)
             p = p-&gt;next;

          // insert after p
          p-&gt;next = new chainNode&lt;T&gt;(theElement, p-&gt;next);
       }
       listSize++;
    }



    template &lt;class T&gt;
    void chain&lt;T&gt;::Split(chain&lt;T&gt;&amp; A, chain&lt;T&gt;&amp; B, chain&lt;T&gt;&amp; C)

    {// Split A into two chains B and C.

     // When done, A is unchanged.

       // first free all nodes in B and C

         // find firt node of A

     //  B.erase();
        int j;
        j=0 ;
        listSize = B.listSize;
       for (j=0 ; j &lt; listSize; j++)
           B.erase(0);

      // C.Erase();
       j=0 ;
        listSize = C.listSize;
       for (j=0 ; j &lt; listSize; j++)
           C.erase(0);

        for (chain&lt;T&gt;::iterator b = A.begin();
            b != A.end(); b++)
          cout &lt;&lt; "A from in " &lt;&lt; *b &lt;&lt; "  ";

       // assign elements alternately to B and C
       int n=0;
       chain&lt;T&gt;::iterator a = A.begin();
       chainNode&lt;T&gt;  *current;

         while (a != A.end()) {
             B.insert(n,*a);// first give B an element
             a++;

          if (a == A.end()) break;
               C.insert(n,*a); // now give C an element

           a++;
           n=n+1;
           }

    }



    // chain node

    #ifndef chainNode_
    #define chainNode_

    template &lt;class T&gt;
    struct chainNode 
    {
       // data members
       T element;//data 
       chainNode&lt;T&gt; *next;//link

       // methods
       chainNode() {}
       chainNode(const T&amp; element)
          {this-&gt;element = element;}
       chainNode(const T&amp; element, chainNode&lt;T&gt;* next)
          {this-&gt;element = element;
           this-&gt;next = next;}
        };

    #endif
</code></pre>
