1
\$\begingroup\$

Routine to merge two linked lists together and return a new merged list. One optimization I can think of is passing by reference instead of value. Any other suggestions ? Is there a shorthand to make lines 4 and 5 single/shorter?

template<class t>
Linkedlist<t> merge(Linkedlist<t> firstList, Linkedlist<t> secondList) {

/*4*/   Node<int> * current = ( firstList.head->data < secondList.head->data ) ? firstList.head : secondList.head;
/*5*/   Node<int> * other = ( firstList.head->data > secondList.head->data ) ? firstList.head : secondList.head;

    Node<int> * oldOther = nullptr;
    Node<int> * oldNext = nullptr;

    while ( current && other ) {
        if ( current->next == nullptr || current->next->data > other->data ) {
            oldOther = other;
            oldNext = current->next;
            current->next = other;
            other = oldNext;
            current = oldOther;
        } else {
            current = current->next;
        }
    }

    return ( firstList.head->data < secondList.head->data ) ? firstList : secondList;
}
\$\endgroup\$
1

3 Answers 3

4
\$\begingroup\$

Your code has three issues I can see.....

  1. the stated goal is to return a new list, but your code returns one of the input lists that have been modified to have the merged results. This is buggy.
  2. If the first two elements in each list are equals, your initialization process will fail, one of the comparisons, either the first, or the second has to have an = component, either <= or >=. As it stands, both the current and the other will point to the secondList if the first values are equals.
  3. What's Node<int>? Why is it not Node<t>? Why use templates at all if you have only one template type that works?
\$\endgroup\$
4
  • \$\begingroup\$ Would you say the code is broken? \$\endgroup\$
    – Emily L.
    Oct 13, 2015 at 11:26
  • \$\begingroup\$ @EmilyL. - yes, I would, but, I also believe the OP thinks it works. It will likely produce the right results for the inputs they test with. So, it is not broken-code to the point of being off-topic. \$\endgroup\$
    – rolfl
    Oct 13, 2015 at 11:28
  • \$\begingroup\$ Thanks for the insights @rolfl . Node<int> is just some leftover debug code I missed to get rid of \$\endgroup\$
    – Nash Vail
    Oct 13, 2015 at 11:33
  • \$\begingroup\$ Sometimes I find it hard to judge if OP genuinely thinks it works or just hopes that we'll debug it for them. Text is such a difficult medium for human communication... \$\endgroup\$
    – Emily L.
    Oct 13, 2015 at 12:11
2
\$\begingroup\$

First the lists you pass have generic parameter t while the nodes have parameter int. This feels like an error.

Second you don't clear the list you don't pass back (setting ->head to null) which means that it will destroy its nodes (which are now part of the list you returned) leaving the list you return with a dangling pointer that will end up double freed. I would recommend not accessing the innards of the linked list in general.

\$\endgroup\$
1
\$\begingroup\$

I see a number of things which may help you improve your code.

Make template arguments consistent

Your Merge routine takes a pair of Linkedlist<T> arguments, but then seems to assume that they are really Linkedlist<int> because of the Node<int> declarations. If you're going to use a template, make sure it's consistent and useful.

Don't directly manipulate object data

The code seems to assume that all member data items are public which is generally not a good design. A better idea is to use accessors or functions to allow safer object operation and to allow different kinds of objects to be used. In this case, it was not that easy to review the code because the interface was not fully specified.

Avoid the use of raw pointers

In modern C++, raw pointers are generally an indicator that your design could likely be improved. In this case, for example, what happens if your code is passed an empty list? The likely result will be a crash because the first thing the code does is to dereference the head pointer. If that pointer is nullptr then a crash is a likely result.

Prefer to pass by reference

The lists probably don't actually need to be copied to perform the merge. For that reason, it would be better to declare the function as:

Linkedlist<t> merge(const Linkedlist<t> &firstList, const Linkedlist<t> &secondList) {

Decide which object owns the data

In the merge code as implemented, two well formed lists are passed in and then their data is scrambled. When the temporary Linkedlist parameter objects are deleted at the end of your function, all of their contents and pointers are invalidated making the returned list useless, since it will have references to deleted objects. This will result in a crash or memory leak at best.

Include test code in your review request

It's often much easier to review code if it is shown in context and with a complete interface. In this case, reviewers are left to reverse engineer the possible contents and operation of the Node<T> and Linkedlist<T> templates.

Consider implementing iterators

If your LinkedList class implemented iterators, much of the messy pointer dereferencing would be eliminated and the code would be much easier to see and understand. It would also make it possible to use standard algorithms to manipulate your Linkedlist class. See this question for hints on how to do that.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.