how to empty the linked list after union operation

[djhyun0001]

hi,

my union operation function should empty out the two lists from the parameter after the operation and have to handle when one of the list is the current list. it has to be o(n). any hint would be appreciated.

//----------------------------------------------------------------------------
// merge
// Takes 2 sorted lists and merge into one long sorted list
// @pre   : head point to the first node in list
// @post  : current list becomes the merged list of the two parameter lists and
//          two parameter list becomes empty unless one is also the current
//          object
// @param : left, list to be merged
// @param : right, list to be merged
// @return: none
template <typename T>
void List<T>::merge(List& left, List& right)  {
    // handle when either one of the lists is NULL
    if (right.head == NULL)  {
        if (&left != this)  {
            makeEmpty();
            copyList(left);
        }
    }
    else if (left.head == NULL)  {
        if (&right != this)  {
            makeEmpty();
            copyList(right);
        }
    }
    else if (right.head == NULL && left.head == NULL)  {
        makeEmpty();
    }
//    else if (&left == this)  {
//        
//    }
    else {
        // create temps
        Node* leftHead = left.head;
        Node* rightHead = right.head;
        
        // assign the node with smallest data as the head
        if (*leftHead->data < *rightHead->data)  {
            head = leftHead;
        }
        else  {
            head = rightHead;
            rightHead = leftHead;
            leftHead = head;
        }
        
        // place the node in correct location, order by node->data
        while (leftHead->next != NULL && rightHead != NULL)  {
            if (*leftHead->next->data > *rightHead->data)  {
                Node* temp = leftHead->next;
                leftHead->next = rightHead;
                rightHead = temp;
            }
            leftHead = leftHead->next;
        }
        
        // finish merge by linking the right
        if (leftHead->next == NULL)  {
            leftHead->next = rightHead;
        }
//        left.makeEmpty();
//        right.makeEmpty();
    }
}

[Ispil]

What other operations do your linked lists already have?

[djhyun0001]

I think I can just call the makeEmpty function, but I get pointer being freed was not allocated error. my buildList, insert, and makeEmpty are on below.

//----------------------------------------------------------------------------
// buildList
// continually insert new items into the list
// @pre   : head point to the first node in list
// @post  : each data from the file is added as node to the list with correct
//          size and in order.
// @param : infile, file stream
// @return: none
template <typename T>
void List<T>::buildList(ifstream& infile) {
    T* ptr;
    bool successfulRead = false;
    bool success = false;
    
    // infinite until reading the end of file
    for (;;) {
        ptr = new T;
        successfulRead = ptr->setData(infile);
        if (infile.eof()) {
            delete ptr;
            break;
        }

        // insert good data into the list, otherwise ignore it
        if (successfulRead) {
            success = insert(ptr);
        }
        else {
            delete ptr;
        }
        if (!success) break;
    }
}

//----------------------------------------------------------------------------
// insert
// Insert an item into list
// @pre   : head point to the first node in list
// @post  : a node with data from the parameter is added on the list
// @param : dataptr, pointer to the data of the node
// @return: return boolean value tath determine whether insert is success
template <typename T>
bool List<T>::insert(T* dataptr) {
    
    Node* ptr= new Node;
    
    // check invalid
    if (dataptr == NULL) return false;
    
    // link the node to data
    ptr->data = dataptr;
    
    // if the list is empty or if the node should be inserted before
    // the first node of the list
    if (isEmpty() || *ptr->data < *head->data) {
        size++;
        ptr->next = head;
        head = ptr;
    }
    
    // then check the rest of the list until we find where it belongs
    else {
        Node* current = head->next;
        Node* previous = head;
        
        // walk until end of the list or found position to insert
        while (current != NULL && *current->data < *ptr->data) {
            previous = current;
            current = current->next;
        }
    
        // insert new node, link it in
        size++;
        ptr->next = current;
        previous->next = ptr;
    }
    return true;
}
//----------------------------------------------------------------------------
// makeEmpty
// empty out the list, deallocate all memory for all Nodes and each Object
// for class List
// @pre   : head point to the first node in list
// @post  : each node in the linked list for List is deallocated, head is NULL
// @param : none
// @return: none
template <typename T>
void List<T>::makeEmpty() {
    Node* current = head;
    Node* next;
    
    // iterate through the list and delete each node
    while (current != NULL) {
        next = current->next;
        delete current;
        current = next;
    }
    head = NULL;
    size = 0;
}