Merging Linked Lists

my head hurts so much...
I'm having a lot of problems with this. I know the answer is so simple, but I just can't figure it out. I'm trying to take two presorted linked lists, and combine them into one sorted linked list. Here's what I've got so far. As always, it's my logic that's the error.

list definition:

struct DblNode
{
int Data;
DblNode *Next, *Prev;
};

merging function:

void MergeLists(DblNode* &resList, DblNode* &fListOne, DblNode* &fListTwo)
{
DblNode *curRes, *curFirst, *curSecond;
resList = new DblNode;
curRes = resList;
curFirst = fListOne;
curSecond = fListTwo;
while(curFirst->Next != NULL || curSecond->Next != NULL)
{
curRes = new DblNode;
if(curFirst->Data < curSecond->Data)
{
curRes = curFirst;
curRes->Next = curSecond;
curRes = curRes->Next;
}
else
{
curRes = curSecond;
curRes->Next = curFirst;
curRes = curRes->Next;
}
curFirst = curFirst->Next;
curSecond = curSecond->Next;
}
if(curFirst->Next == NULL)
{
while(curSecond->Next != NULL)
{
curRes = new DblNode;
curRes = curSecond;
curRes = curRes->Next;
curSecond = curSecond->Next;
}
}
else
{
while(curSecond->Next != NULL)
{
curRes = new DblNode;
curRes = curSecond;
curRes = curRes->Next;
curSecond = curSecond->Next;
}
}
curRes->Next = NULL;
}

the code I've got here so far is only supposed to link the list with the Next pointer, not the Prev. The reason for this is because if I can't figure out how to do that, why should I clutter it up with some more errorous code? Thanks for the help guys.

As a general rule you should always check the return of any pointer. Like in your new you allocate and assume there's a value. While in this case new will throw a bad_alloc if it fails and you'll never get a chance to check the return. But it is a VERY good habit to get into.

Enough evangelizing.... Just after a quick look in a Merging of two lists there should never be a need to create any new nodes, since you are just merging. All you should be doing is adjusting the existing pointers. And a big clue is always keep the current_pointer, and previous_pointer for your insertion.

Personally I would just create a new linked list from the two with a loop to read from them into it. Mainly like a constructor with arrays of head nodes, then it would loop threw each head node adding data until it reached the end.

Just depends on what you are using it for though. If you are going to be working with large lists a merge function would be overall better then the above listed.

You could do it that way but it would not be a very effiecient approach. Remember every call to new calls the object's constructor and if its derived it calls that constructor and so on.... As well as each delete calls the respective destructor.

Also, with every call to new the memory pool is searched for a block of memory large enough to satisfy the request. This is done by checking a map or directory of some sort that show which blocks are currently availible. It's a quick process but it just one more thingy....