in place merge sort for linked list

[Denny001]

Hi,
this is in-place merge sort, for merge function. Can you tell me, there is something wrong. thanks

LinkedListNode::LinkedListNode(int value) {
this->next = NULL;
this->value = value;
}


LinkedListNode *mergeSortedLinkedLists(LinkedListNode *firstList, LinkedListNode *secondList)

{
LinkedListNode* head, *ptr;
head=new LinkedListNode(NULL);
ptr=head;
//head=firstList;
//ptr=head;
while ( (firstList!=NULL) && (secondList!=NULL))
{
if ( (firstList->value) <= (secondList->value) )
{
ptr=firstList;
firstList=firstList->next;
}
else
{
ptr=secondList;
secondList=secondList->next;
}
ptr=ptr->next;
}
while (firstList==NULL)
{
ptr=secondList;
}
while (secondList==NULL)
{
ptr=firstList;
}
return head->next;

}

[Duthomhas]

Something that is difficult with loops is the idea of invariants. Certain things need to be true all the time.

Figuring out what those things are will help.

The idea is to merge two sorted lists into a single sorted list.

During your loop, you will need:
- pointer to the current head of list 1
- pointer to the current head of list 2
- pointer to the head of the result
- pointer to the current tail of the result

This implies the following invariant:
- the tail is a member of the result list.

That is, if you were to stop the loop at any time and try to find the tail from the head, you could. If you break this anywhere in the loop (and you do) then the function will fail.


The next thing to notice is that it is much easier to handle stuff when you have a known to exist element at all times in the result. That way, to add an element to the result, all that is needed is to assign to the current tail's 'next' pointer. This saves you from having to do stuff like check to see if head and tail are null or not, and special code for if they are. This adds two invariants to our code:

INVARIANTS
- the tail is a member of the result list.
- the result head points to a valid node.
- the result tail points to a valid node.

Here's the trick that your code tries to do. The head points to a node, but the head node is not part of the result and it's value is meaningless. (That's why you return head->next.)


Okay, so on to the code. You create a new node for the result's dummy head. Don't do that. There is no reason to allocate dynamic memory for the head. (And what happens is that it doesn't get deleted, which is a memory leak.)

Just create a normal variable in your function, and point the result head at it.

LinkedListNode* head;
LinkedListNode* tail;  // you named this 'ptr'

LinkedListNode foo;  // Here's the dummy head node
head = &foo;
tail = &foo;

// Make sure that the result is currently NO LIST. 
head->next = NULL;

...

Next, when you add an element to the result list, you need to append it to the list. (So, how do you do that? Remember the invariants!)

Hint: There are four places where you say ptr= that you need to fix.


Finally, before you return, you need to make sure that the next element at the end of the list is NULL (since there is no next element).


Hope this helps.

[Denny001]

thanks

I re-write it. can you help me check it again?

[Duthomhas]

Sure. Have you tried it to see if it works?