2
\$\begingroup\$

I'd like to see if there's any code reuse I'm missing, or anything else that can be rewritten in a better way, but always following the same data structures (without adding more classes or using the C++ list implementation).

Node* merge(Node* list1, Node* list2){
    if (list1 == nullptr){
        return list2;
    }
    else{
        if (list2 == nullptr){
            return list1;
        }
        else{
            Node* newList = nullptr;
            if (list1->data <= list2->data){
                newList = list1;
            }
            else{
                newList = list2;
            }
            while (list1->next != nullptr) {
                if (list1->next->data > list2->data){
                    Node* aux = list1->next;
                    list1->next = list2;
                    list2 = aux;
                }
                list1 = list1->next;
            }
            if (list1->next == nullptr){
                list1->next = list2;
            }
            return newList;
        }
    }
}
\$\endgroup\$
3
  • \$\begingroup\$ I deleted my answer because using iterators in this case would introduce very weird and hard to follow iterator invalidation rules. \$\endgroup\$ Commented Apr 17, 2017 at 16:41
  • \$\begingroup\$ I just realized there's a bug in this code... if list1 has elements: 2-3-4-9 and list2 has elements: 0-1-8 then the merged list omits the 2. \$\endgroup\$ Commented Apr 24, 2017 at 15:34
  • \$\begingroup\$ This would have been a better question if you'd shown the definition of Node so we don't have to infer it - even better would be a complete program with a main() to run a few tests, then we could verify our suggestions before posting. \$\endgroup\$ Commented May 4, 2017 at 12:13

2 Answers 2

Reset to default
4
\$\begingroup\$

I would do a couple of things differently.

Early escape

Your use of early escape is good and makes the code easier to read but you don't need the else section if the body of if statement returns.

Node* merge(Node* list1, Node* list2)
{
    if (list1 == nullptr){
        return list2;
    }
    if (list2 == nullptr){
        return list1;
    }
    // Main body of code.

This is quite normal. It reduces the number of level of indenting and makes the code look clean.

Self documenting code

I would encourage you to split getting the next item into a separate function (this facilitates self documenting code).

Node* getNextNode(Node*& list1, Node*& list2)
{
    // Work out which list has the smallest value.
    Node*& smallList = (list1->data < list2->data) ? list1 : list2;

    // The head of this list is the result
    Node* result = smallList;

    // Move the list to the next value (notice the call be reference).
    smallList = smallList->next;

    return result;
}

Simplified Body

Now if we rewrite the main body of your code in terms of this helper function;

Node* result  = getNextNode(list1, list2);
Node* current = result;

// Looping over the list until one is empty
// becomes very trivial now.
while(list1 != nullptr && list2 != nullptr)
{
     // Get next node and remove it from its list.
     Node* next    = getNextNode(list1, list2);
     current->next = next;
     current       = next;
}

// One of the lists is empty.
// Add what is left of the other list on the end (ie after current).
current->next = (list1 == nullptr) ? list2 : list1;
return result;
\$\endgroup\$
1
\$\begingroup\$

As a general note, avoid needless indentation. Control-flow already leaves the function after return, so no need to open an else-block. Twice.

Use the power of double-indirection and you can remove all the special-cases:

Node* merge(Node* list1, Node* list2){
    Node* result;
    Node** current = &result;
    while(list1 && list2) {
        Node*& next = list2->data < list1->data ? list2 : list1;
        *current = next;
        next = next->next;
        current = &(*current)->next;
    }
    *current = list1 ? list1 : list2;
    return result;
}

As an aside, I'm using < instead of <= just like the standard library does.

\$\endgroup\$
5
  • 1
    \$\begingroup\$ Assuming you just want to make it harder to read. The special cases make the code simple to read and don't degrade performance in any way so there seems no pressing reason to remove them. Then using this double indirection seems doubly as unpleasant to read. \$\endgroup\$ Commented Apr 17, 2017 at 16:13
  • \$\begingroup\$ I think you are forgetting the mission of the site. The point is to encourage best practices not premature optimization or an attempt to write the most compressed form of the code we can find and definitely not to try and make an expressive language like C++ look like yesterdays C code. \$\endgroup\$ Commented Apr 17, 2017 at 16:21
  • 1
    \$\begingroup\$ Double-pointers aren't poison. True, you don't want to be a five-star-programmer, but one can take it too far in the other direction too! Well, I've used longer names now, there was no reason to be stingy there... \$\endgroup\$ Commented Apr 17, 2017 at 20:51
  • \$\begingroup\$ Double de-referencing has its place. But this is just not it. You are skewing way to far towards premature optimization. Good practice is to write readable code first (not pre-optimized code). \$\endgroup\$ Commented Apr 17, 2017 at 22:31
  • \$\begingroup\$ You are doing double-indirection too, through a Node* instead of a Node**, and thus you need to handle the head separately. That's no win. \$\endgroup\$ Commented Apr 21, 2017 at 17:07

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.