Merge linked lists

Question

I am trying to merge two linked lists in c++ without in place. But everytime the new list created emits out the following numbers after it reaches the nullptr for one or the other list.

MyLinkedList mergeTwoLinkedList(MyLinkedList b) {
        MyLinkedList c;

        node *tempa = this->head;
        node *tempb = b.head;

        if (b.head == nullptr)
            return *this;

        if (this->head == nullptr)
            return b;

        if (tempa && tempb) {
            do
            {
                if ((tempa->val) <= (tempb->val)) {
                    c.addAtTail(tempa->val);
                    tempa = tempa->next;

                } else if ((tempa->val) >= (tempb->val)) {
                    c.addAtTail(tempb->val);
                    tempb = tempb->next;
                }
            }
            while (tempa && tempb);
            return c;
        }
}

Not sure this is your problem, but if your program reaches `tempa && tempb` and that is false (although I think that might be impossible because of your other if statements), [your program results in undefined behavior](https://stackoverflow.com/q/2598084/10957435). — , Aug 09 '19 at 03:09
`But everytime the new list created emits out the following numbers after it reaches the nullptr` what numbers? — , Aug 09 '19 at 03:11
After `while (tempa && tempb);` you should see if either `tempa` or `tempb` are not null and add all remaining nodes to `c` — drescherjm, Aug 09 '19 at 03:12
There are multiple problems in toyr code. In addition to the discovered above: how is the `addAtTail` implemented? If you add to the actual end of the list, that means that you are adding to the end of either `tempa` or `tempb`. — Dmitry Kuzminov, Aug 09 '19 at 03:17

score 2 · Answer 1 · answered Aug 09 '19 at 04:30

This is a very common pattern for merge sort. Let me simplify your loop first, by removing the redundant test (because if value A is NOT less than equal to B then by definition it is greater than).

while (tempa && tempb)
{
    if (tempa->val <= tempb->val) {
        c.addAtTail(tempa->val);
        tempa = tempa->next;
    } else {
        c.addAtTail(tempb->val);
        tempb = tempb->next;
    }
}

So, what's going to happen is that as soon as either list reaches the end, your loop will finish and no more values are added.

The absolute simplest and most readable solution to this problem, in my opinion, is to add two more loops afterward, which just append the remaining tails:

for(; tempa; tempa = tempa->next)
{
    c.addAtTail(tempa->val);
}

for(; tempb; tempb = tempb->next)
{
    c.addAtTail(tempb->val);
}

It is common to see other solutions, where the main loop doesn't terminate until both pointers are NULL, but this requires more tests inside the loop that potentially reduce performance and definitely reduce readability.

Now, if you are indeed using this for merge sort, you don't even need a separate list. You can just merge one list into another by patching the list nodes. That makes adding the entire tail an O(1) operation, and it means no allocations happen during merge. I'll leave that as an exercise for you, if appropriate.

score 1 · Answer 2 · answered Aug 09 '19 at 04:49

Assuming the addToTail() is defined correctly. There is a flaw in the code you showed. In the loop:

do
{
    if ((tempa->val) <= (tempb->val)) {
        c.addAtTail(tempa->val);
        tempa = tempa->next;

    } else if ((tempa->val) >= (tempb->val)) {
        c.addAtTail(tempb->val);
        tempb = tempb->next;
    }
} while (tempa && tempb);

The while condition is checking for tempa && tempb --> you are checking both of them to be valid. There may be a case where one list has more nodes than the other. In that case you are missing out to copy nodes from other list. To correct this flaw, you can change the code as follows:

MyLinkedList mergeTwoLinkedList(MyLinkedList b) {
    MyLinkedList c;

    node *tempa = this->head;
    node *tempb = b.head;

    if (b.head == nullptr)
        return *this;

    if (this->head == nullptr)
        return b;

    if (tempa && tempb) {
        do
        {
            if ((tempa->val) <= (tempb->val)) {
                c.addAtTail(tempa->val);
                tempa = tempa->next;

            } else if ((tempa->val) >= (tempb->val)) {
                c.addAtTail(tempb->val);
                tempb = tempb->next;
            }
        }
        while (tempa && tempb); /* here  one of the tempa or tempb list may still have some nodes to copy to 'c' list */

        if (tempa) { // checking whether tempa list has more nodes to cover
            while (tempa) {
                c.addAtTail(tempa->val);
                tempa = tempa->next;
            }
        } else if (tempb) { // checking whether tempb list has more nodes to cover
            while (tempb) {
                c.addAtTail(tempb->val);
                tempa = tempb->next;
            }
        }
    }
    return c;       // returning the new list after merging
}

This should solve your problem. Hope this helps, thanks :)

Merge linked lists

2 Answers2