merge two sorted linked list

[i_luv_c++]

Hey guys! I am working on a project using single linked list and currently on the last task which is overloading the += operator. My merge from a+=b is inefficient because I am having a memory link problem and its slow when it used in list size of 100000. Please let me know if you guys see a error. Thanks for all the help!

//overloaded plus equal (+=) operator
	OList & operator += (const OList & other) { 
	
	Node<T> *temp,
			*p1 = head, //list on the left of operation a+=b
			* p2 = other.head;	//list on the right 
	
	size += other.size;	//change size of current list to list suze += right list size
	
	//data hold the data for the Node and next points to next node 
	while ( p2->next != NULL && p1->next != NULL ) {
		if (p1->next->data <= p2->next->data) {	
			p1= p1->next;	
			
		}
		else{temp = createNode(p2->next->data);
			temp->next = p1->next;
			p1->next = temp;
			p1 = p1->next;
			p2 = p2->next;
			}
	}
	while (p1->next != NULL) {
		p1 = p1->next;
	}
	while (p2->next != NULL) {
			p1->next = createNode(p2->next->data);
			p1 = p1->next;
			p2 = p2->next;
			if (p1->next == NULL) lastNode = p1;
		}
	lastNode = p1;
	return *this;
		
	}

[mike_2000_17]

There is one thing to observe. What is really expensive in your code (and in many linked-list implementation) is the very frequent dynamic allocation of memory of small chunks (each node). Because you know, from the start of this function, how much memory you will end up allocating for the additional amount of nodes in the LHS list, you should find a way to use that information to your benefit. However, the structure of a linked-list makes this very difficult (i.e. ideally, you would want to allocate a large block of memory, and use placement-new operator to create your new nodes in that space, but the book-keeping that this will require is a going to be very difficult to implement). So, you really are stuck having to do all these incremental and numerous dynamic memory allocations.

For the rest, your algorithm seems to be doing what it should and I can't think of a way to accomplish that more efficiently.

However, you can accomplish something slightly different much much more efficiently. If you implement move-semantics instead of copy-semantics for your linked-list, you can avoid the memory allocation completely. By "move-semantics" I mean that the RHS list would be transferred into the LHS list as they are merged together. If you take the RHS list as a non-const reference, you could basically just empty out the nodes of that list and link them to the nodes in your LHS list. At the end, the RHS list will be empty (head == NULL), and now, the LHS list will be responsible for deleting the nodes that have been transferred to it. The "move-semantics" are almost always much more efficient, and very often it corresponds to what you would want to use this merge function for, e.g. went merging two sorted lists, you most often want to end up with one big merged list and don't really care about keeping the RHS list intact (but, I would not use += operator for that, because it could be confusing, you would be better off giving it a sensible name like "mergeInto()" or something).

[WolfPack]

Lines 23 to 25 in your code seems to be useless. I don't think there is the need to move to the end of List1 in order to update LastNode which needs no updating.
Did a rewrite. Maybe buggy since I don't have the class declaration of node, so use it as an algorithm at best.

//overloaded plus equal (+=) operator
//data hold the data for the Node and next points to next node 
OList & operator += (const OList & other) { 
    Node<T> *temp;
    Node<T> *p1 = head;         //list on the left of operation a+=b
    Node<T> *p2 = other.head;    //list on the right 
    
    size += other.size;    //change size of current list to list size += right list size
    
    // Assumes P1 and P2 are already sorted

    // Haven't reached the end of List1 or List2?
    while ( p1 != NULL && p2 != NULL ) { 
        // For each P2 in List2, find P1 in List1 where P1.data > P2.data, and insert P2
        if (p1->data > p2->data) {
            temp = createNode(p2->data);
            temp->next = p1->next;
            p1->next = temp;
            p2 = p2->next; // Advance to the next item in List2
        }
        p1 = p1->next; // Advance to the next item in List1
    }
    if (p2 == NULL){ // End of List2 reached or List2 was empty from the start
        // All elements of p2 have been inserted to List1.
        // Nothing else to do.
    }
    else{ // Some items are left in List2
        // Append copies of remaining items to List1
        while (p2 != NULL){
            temp = createNode(p2->data);
            temp->next = p1->next;
            p1->next = temp;
            p2 = p2->next;
        }
        lastNode = p1; // Update LastNode
    }
    return *this;
}

EDIT:
Your code is fine. My code is buggy.
And lines 23 to 25 are required. Apologies.