Merging of two linked list to join a larger list l3

QUESTION 

Suppose we have singly, sorted, linear, linked lists with a head pointer.  Given two such sorted linked lists, construct a third linked list which is also sorted and contains all the nodes of the original two lists.  If you use any other method then provide its implementation too.   The complexity of your function must be O(m+n) where m is the total nodes in list 1 and n is the total nodes in list 2.  The following declarations are provided:

You do not have to write the code for the implemented methods. 

class Node {             Node *next;             int Data;             friend class LinkedList; };

class LinkedList { public:             LinkedList();  //implemented             ~LinkedList(); //implemented             LinkedList(const LinkedList &L); //implemented             const LinkedList & operator = (const LinkedList &rhs); //implemented             LinkedList Merge(LinkedList &L); //you have to implement             //add any other method you like but implement it too private:             Node *head; };

You have to implement the merge function.  An example is given below:

L1 is the following list:

L2 is the following list:

L3 = L1.merge(L2) should construct and return L3 as:

SOLUTION

NOTE: This is one possible solution and necessarily the best one.  I am sure you can find a better solution

LinkedList LinkedList::Merge(LinkedList &L)

{

            LinkedList ResultList;

            Node *ResultPtr = NULL, *thisPtr = head, *LPtr = L.head;//ResultPtr will point to last link of list

                                                                                    //thisPtr will iterate through this

                                                                                    //LPtr will iterate through nodes of L

            while (thisPtr || LPtr)

            {

                        //create a new node for result list

                        Node *newNodeOfResult = new node;//will create the last node of result list

                        newNodeOfResult->next = NULL;   //we will fill the data value later

                       

                        //if head node does not exist

                        if (!Result.head)

                        {

                                    Result.head = newNodeOfResult;

                                    ResultPtr = Result.head;

                        }         

                        else                 

                        {          //maintain the previous and next of of result list

                                    ResultPtr->next = newNodeOfResult;

                                    ResultPtr = newNodeOfResult;

                        }

                        if (!LPtr || (thisPtr && LPtr && (LPtr->Data > thisPtr->Data))

                        {          //if either LPtr is NULL or data in LPTR is greater than that of thisPtr

                                    //then copy data of thisPtr  in new node and advance thisPtr

                                    ResultPtr->Data = thisPtr->Data;

                                    thisPtr = thisPtr->next;

                                   

                        }

                        else

                        {          //will enter this case if either thisPtr is NULL or if data in thisPtr is greater than

                                    //that of LPtr

                                    ResultPtr->Data = LPtr->Data;

                                    LPtr = LPtr->next;

                        }

            }

            return ResultList;

}