Merge two sorted linked lists without recursion

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 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 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;
}

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 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).

StackExchange Code Review Q#113460, answer score: 3