Union and Intersection of two Linked Lists in C++

#include <iostream>

using namespace std;

class LinkedList
{
    //Linked List Node
    struct node
    {
        int data;
        node *next;
    };

    //Header Node that points to linked list
    node* header;

    //Utility Function to free memory allocated to the nodes
    void freeMemory()
    {
        node * t;
        while(header != NULL)
        {
            t = header;
            header = header->next;
            delete t;
        }
        header = NULL;
    }

    //Utility Function to check the presence any data in the list
    bool isPresent(int data)
    {
        node *t = header;

        while ( t != NULL )
        {
            if(data == t->data )
                return true;
            t = t->next;
        }

        return false;
    }

public:
    //Default Constructor
    LinkedList():header(NULL) {}

    //Copy Constructor
    LinkedList(const LinkedList &cp)
    {
        node *t = cp.header, *t2;
        header = NULL;
        while(t != NULL)
        {
            t2 = new node;
            t2->data = t->data;
            t2->next = header;
            header = t2;
            t = t->next;
        }

    }

    //Overloaded Assignment Operator
    LinkedList& operator=(const LinkedList &cp)
    {
        if(&cp == this)
            return *this;
        //LinkedList();
        freeMemory();
        node *t = cp.header, *t2;
        header = NULL;
        while(t != NULL)
        {
            t2 = new node;
            t2->data = t->data;
            t2->next = header;
            header = t2;
            t = t->next;
        }

        return *this;

    }

    //Destructor
    ~LinkedList()
    {
        node * t;
        while(header != NULL)
        {
            t = header;
            header = header->next;
            delete t;
        }
        header = NULL;
    }

    //Function that adds element to linked list
    void push(int data)
    {
        node *t = new node;
        t->next = header;
        t->data = data;
        header = t;
    }

    //Displays the linked list in console
    void printList()
    {
        node *t = header;
        while(t != NULL)
        {
            cout<<t->data<<"  ";
            t = t->next;
        }
        cout<<endl;
    }

    //Union Function
    /*
    Algorithim
    1> Create an empty List.
    2> Traverse list1 and add all of its elements to the result.
    3> Traverse list2. If an element of list2 is already present
       in result then do not insert it to result, otherwise insert.
    Time Complexity : O(mn) m is the number of elements in first
       list and n is the number of elements in second list.
    */
    LinkedList unionList(LinkedList list2)
    {
        node *t1= header, *t2 = list2.header;
        LinkedList result;

        while(t1 != NULL)
        {
            result.push(t1->data);
            t1 = t1->next;
        }

        while(t2 != NULL)
        {
            if(!result.isPresent(t2->data))
                result.push(t2->data);
            t2 = t2->next;
        }

        return result;

    }

    //Intersection Function
    /*Algorithim
    1> Create an Empty List.
    2> Traverse list1 and look for its each element in list2,
       if the element is present in list2, then add the element to result
    Time Complexity : O(mn) m is the number of elements in first
       list and n is the number of elements in second list.
    */
    LinkedList intersectList(LinkedList list2)
    {
        node *t1= header;
        LinkedList result;

        while(t1 != NULL)
        {
            if(list2.isPresent(t1->data))
                result.push(t1->data);
            t1 = t1->next;
        }

        return result;
    }

};

int main()
{
    LinkedList list1;
    list1.push(10);
    list1.push(30);
    list1.push(12);
    list1.push(19);
    list1.push(78);
    cout<<"List1 : ";
    list1.printList();

    LinkedList list2;
    list2.push(30);
    list2.push(121);
    list2.push(19);
    list2.push(89);
    cout<<"List2 : ";
    list2.printList();

    LinkedList listUnion = list1.unionList(list2);
    cout<<"Union List : ";
    listUnion.printList();

    LinkedList listIntersect = list1.intersectList(list2);
    cout<<"Intercestion List : ";
    listIntersect.printList();


    return 0;
}

Output :-

List1 : 78  19  12  30  10
List2 : 89  19  121  30
Union List : 89  121  10  30  12  19  78
Intercestion List : 30  19

Nth last element in Linked List (C++)

The following code shows how to get nth last element in a linked list. It uses a queue to hold the temporary elements.

Algorithm:-
1>Make a queue of length N
2>Traverse the linked list from root
3>While traversing, en-queue first N elements
4>After this for en-queuing every element, de-queue another element.
5>When we reach the end of linked list, the last de-queued element will be the Nth last element.

/* 
 * File:   main.cpp
 * Author: Asit
 *
 * Created on 16 September, 2011, 12:25 AM
 */

#include <cstdlib>
#include <iostream>
#include <queue>

using namespace std;

struct node
{
    int data;
    node *next;
};

class LinkedList
{
    node *root;
public:
    LinkedList():root(NULL){}
    void add(int x)
    {
        node *temp = NULL;
                
        if(root==NULL)
        {
            root = new node;
            root->data = x;
            root->next = NULL;
        }
        else
        {
            temp = root;
            while(temp->next != NULL)
            {
                temp = temp->next;
            }
            
            temp->next = new node;
            temp = temp->next;
            temp->data = x;
            temp->next = NULL;
        }
    }
    
    void show()
    {
        node *temp = root;
        
        while(temp != NULL)
        {
            cout<<temp->data<<"  ";
            temp = temp->next;
        }
        cout<<endl;
    }
    
    int nthLast(int n)
    {
        queue<node*> t_queue;
        int i=1, t_data = -1;
        node *temp = root;
        
        while(temp != NULL)
        {
            t_queue.push(temp);
            if(i>=n)
            {
                t_data = (t_queue.front())->data; 
                t_queue.pop();
            }
            i++;
            temp = temp->next;
        }
        
        i--;
        if(i<n)
            cout<<"Linked list contains less than "<<n<<" elements"<<endl;
        
        return t_data;
    }
};

int main(int argc, char** argv) 
{
    LinkedList list;
    
    for(int i=0; i<20; i++)
        list.add(i*7+90);
    
    cout<<"Created linked list is .. "<<endl;
    list.show();
    
    cout<<"3rd last element : ";
    
    cout<<list.nthLast(3)<<endl;
    
    return 0;
}

Output:-

Created linked list is .. 
90  97  104  111  118  125  132  139  146  153  160  167  174  181  188  195  202  209  216  223  
3rd last element : 209