Merge two sorted linked lists without recursion

Question

Is this an effective way for merging two lists? It seemed too long.

struct Node {
    int item;
    Node *next;
};

Method:

Node* mergeTwo(Node* headA, Node* headB)
{
Node* currentA = headA;
Node* currentB = headB;

Node* headC = NULL;
Node* currentC = NULL;

while (currentA != NULL && currentB != NULL)
{
    if (currentA->item < currentB->item)
    {
        Node* node = new Node();
        node->item = currentA->item;
        node->next = NULL;

        if (headC == NULL)
            headC = node;
        else
            currentC->next = node;

        // update currents
        currentC = node;        
        currentA = currentA->next;
    }
    else // currentB->item < currentA->item
    {
        Node* node = new Node();
        node->item = currentB->item;
        node->next = NULL;

        if (headC == NULL)
            headC = node;
        else
            currentC->next = node;

        // update currents
        currentC = node;
        currentB = currentB->next;          
    }
}

// one of currentA or currentB will not be NULL
while (currentA != NULL)
{
    Node* node = new Node();
    node->item = currentA->item;
    node->next = NULL;

    // in case like: A={13,15}, B={4,6}
    if (headC == NULL)
        headC = node;
    else
        currentC->next = node;

    // update currents
    currentC = node;
    currentA = currentA->next;      
}

while (currentB != NULL)
{
    Node* node = new Node();
    node->item = currentB->item;
    node->next = NULL;

    // in case like: A={3,5}, B={7,8}
    if (headC == NULL)
        headC = node;
    else
        currentC->next = node;

    // update currents
    currentC = node;
    currentB = currentB->next;  
}
return headC;
}

Answer 1

You're duplicating the code to copy and merge nodes four times - that can't be good. You could move that into a separate function, but that might become messy because of all the state that has to be changed.

An alternative is to rethink your loop a bit. This idea is to loop while either A or B still have elements to avoid the two other whiles in your code. The internal logic can then be simplified to something like:

while ((currentA != nullptr) || (currentB != nullptr)) {
  int next_item;
  if (currentA == nullptr) {
    // A is empty, pick from B
    next_item = currentB->item;
    currentB = currentB->next;
  } else if (currentB == nullptr) {
    // B is empty, pick from A
    next_item = currentA->item;
    currentA = currentA->next;
  } else if (currentA->item < currentB->item) {
    next_item = currentA->item;
    currentA = currentA->next;
  } else {
    next_item = currentB->item;
    currentB = currentB->next;
  }
  // append to list C
}

Still some duplication, but at least it's just two-line blocks without any logic (and no memory allocations).

Also this should be simplified:

Node* node = new Node();
node->item = currentB->item;
node->next = NULL;

Provide a constructor for your node class:

explicit Node(int item) : item{item}, next{nullptr} {} // >= C++11
explicit Node(int item) : item(item), next(NULL) {}    // old C++

(Add a destructor while you're at it, or use smart pointers to avoid leaks.)

Then you can write:

Node* node = new Node(next_item);
if (headC == nullptr) { // or if (!head) { ... }
    headC = node;
} else {
    currentC->next = node;
}
currentC = node;

Last point: make sure you actually need to duplicate the elements. You could avoid all the allocations by re-using the nodes, if the input lists can be trashed (which is usually the case for a merge sort).

Answer 2

Sometimes it's better to just use the standard library. After all, there's a function there just for you: std::merge. Now the problem here is that the <algorithms> library is all iterator based, and we just have Node, so we'll have to write out some iterators. This'll be useful anyway, since if Node is part of a singly-linked-list container that you want to use as a normal C++ container, you'll want iterators.

The goal of all of what follows is to be able to implement merge thusly:

Node* mergeTwo(Node* headA, Node* headB)
{
    return std::merge(
        NodeIterator{headA}, NodeIterator{},
        NodeIterator{headB}, NodeIterator{},
        NodeOutputIterator{}
        );
}    

which is pretty neat. Additionally, it lets you easily extend this function to merge in different orders by just asking for an extra comparator.

---

To make things as easy as possible, we can Boost.IteratorFacade, which makes writing the normal Node iterator simple: we just need to implement increment(), equal(), and dereference():

struct NodeIterator
    : boost::iterator_facade<NodeIterator, int, boost::forward_traversal_tag>   
{
public:
    NodeIterator() noexcept : node(nullptr) { }    
    NodeIterator(Node* n) noexcept : node(n) { }

private:
    friend class boost::iterator_core_access;

    void increment() noexcept { node = node->next; }    
    bool equal(NodeIterator const& other) const noexcept { return node == other.node; }
    int& dereference() const noexcept { return node->item; }

    Node* node;
};

Nothing interesting there, mostly boilerplate. Note: I don't recommend writing actual code all on one line like this, I'm just doing this for demonstration purposes to fit everything vertically better.

Now the tough part is that we need an output iterator. Output iterators are just really weird to write. But basically the important operation that we want to override is assignment. There may be a better way to write this particular output iterator, but as a first go, assignment will effectively do a push back (note: if you have a list container already, NodeOutputIterator should have one as a member):

struct NodeOutputIterator
    : std::iterator<std::output_iterator_tag, int>
{
    NodeOutputIterator() noexcept 
    : head(nullptr), tail(nullptr);
    { } 

    void operator=(int i) {
        Node* next = new Node{i, nullptr};
        if (head) {
            tail->next = next;
            tail = tail->next;
        }
        else {
            head = tail = next;
        }
    }   

    NodeOutputIterator& operator*() noexcept { return *this; }
    NodeOutputIterator& operator++() noexcept { return *this; }
    NodeOutputIterator operator++(int) noexcept { return *this; }
    operator Node*() noexcept { return head; }

    Node* head;
    Node* tail;
};

And that's it. This may technically be longer than Mat's solution - but actually implementing merging is remarkably annoying, so here we focus on just writing simple code. Nothing in either iterator is complicated (outside of why NodeOutputIterator::operator= does a push back), and I like not having to write complicated code.

Answer 3

Your code isn't exception-safe.

That's easiest healed decomposing your operation into two separately useful operations:
Duplicating a list, and destructively merging two lists.

As an aside, I suggest you put the link first, that makes identical code folding more likely, especially when you get around to templating your list on the value-type.

struct Node {
    Node* next;
    int value;
};

void deleteList(Node* list) noexcept {
    while(list)
        delete std::exchange(list, list->next);
}

Node* cloneList(const Node* list) {
    Node* r = nullptr;
    try {
        for(Node** p = &*r; list; p = &p[0]->next, list = list->next)
            *p = new Node{nullptr, list->value};
        return r;
    } catch(...) {
        deleteList(r);
        throw;
    }
}

Node* mergeListDestructively(Node* a, Node* b) noexcept {
    Node* r = 0;
    Node** p = &r;
    while(a && b) {
        Node*& c = a->value > b->value ? b : a;
        *p = c;
        p = &c->next;
        c = c->next;
    }
    *p = a ? a : b;
    return r;
}

Node* mergeList(Node* a, Node* b) {
    a = cloneList(a);
    try {
        return mergeListDestructively(a, cloneList(b));
    } catch(...) {
        deleteList(a);
        throw;
    }
}

Of course, things would be far easier if you put the list inot a RAII-type owning it...

Answer 4

There are three things to make this much easier to write:

1. Use a Node** up front that you append to. This avoids having to do a branch.
2. Keep a reference to the next min node - this makes you only have to append in one spot.
3. Write a copy function

First, the copy function:

void append_all(Node* src, Node** dst) {
    for (; src; src = src->next) {
        *dst = new Node{src->item, nullptr};
        dst = &(*dst)->next;
    }
}

And for the rest - we just loop while we have both pointers:

Node* mergeTwo(Node* headA, Node* headB)
{
    Node* head = nullptr;
    Node** out = &head;

    while (headA) {
        if (!headB) {
            append_all(headA, out);
            return head;
        }

        Node*& min = headB->item < headA->item ? headB : headA;
        *out = new Node{min->item, nullptr};
        out = &(*out)->next;
        min = min->next;
    }

    append_all(headB, out);
    return head;
}