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 &amp;&amp; currentB != NULL)
{
    if (currentA-&gt;item &lt; currentB-&gt;item)
    {
        Node* node = new Node();
        node-&gt;item = currentA-&gt;item;
        node-&gt;next = NULL;

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

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

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

        // update currents
        currentC = node;
        currentB = currentB-&gt;next;          
    }
}

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

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

    // update currents
    currentC = node;
    currentA = currentA-&gt;next;      
}

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

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

    // update currents
    currentC = node;
    currentB = currentB-&gt;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-&gt;item;
    currentB = currentB-&gt;next;
  } else if (currentB == nullptr) {
    // B is empty, pick from A
    next_item = currentA-&gt;item;
    currentA = currentA-&gt;next;
  } else if (currentA-&gt;item &lt; currentB-&gt;item) {
    next_item = currentA-&gt;item;
    currentA = currentA-&gt;next;
  } else {
    next_item = currentB-&gt;item;
    currentB = currentB-&gt;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-&gt;item = currentB-&gt;item;
node-&gt;next = NULL;


Provide a constructor for your node class:

explicit Node(int item) : item{item}, next{nullptr} {} // &gt;= 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-&gt;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).