Convert recursive to iterative function

Question

I have a chained list merge function working. However, recursion is being used and I would like to change the code and iterate. But I was unsuccessful.

Follows the code:

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

struct Node* MergeLists(struct Node *headA,struct Node* headB)
{
if(headA==NULL) return headB;
if(headB==NULL) return headA;
if(headA==NULL && headB==NULL) return NULL;

if(headA->data < headB->data)
{
    headA->next=MergeLists(headA->next,headB);
   return headA;
}
else 
{
    headB->next=MergeLists(headA,headB->next);
    return headB;
}
}

What I’ve got so far is this:

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

  Node* MergeLists(Node *headA, Node* headB)
 {
 if(headA==NULL) return headB;
 if(headB==NULL) return headA;
 if(headA==NULL && headB==NULL) return NULL;
 while(headA!=NULL && headB!=NULL)
 {
    if(headA->data>headB->data)
    {
        return headB;
        headB=headB->next;/*O problema está aqui preciso retornar o valor menor e ao mesmo tempo avançar a lista*/
    }else 
    {
        return headA;
        headA=headA->next;/*O problema está aqui preciso retornar o valor menor e ao mesmo tempo avançar a lista com o return antes ele irá sair sem avançar*/
    }        
    }
    }

NOTE: The two lists are in ascending order.

Ex:

Heada = 1, 3, 5.

Headb = 2, 4, 6.

Mixing = 1, 2, 3, 4, 5, 6.

Answer 1

Stacked, the calls in the code are. When pop-up, the list nodes reconnected. Back-to-front, in their original code, merged the list. In the call stack, the nodes to be connected, stored. No stack concept and no drastic changes, the original, iterative algorithm can not do.

For the iterative algorithm you must necessarily have a new approach:

You must create a new list. From it, the head and the tail, will keep in variables. From back-to-back yes, from back-to-front no, the new list. The knots of headA and headB, at each iteration, from your lists you must remove and at the tail of your new list you will add. Until both lists are empty.

The code, it’s here:

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

struct Node* MergeLists(struct Node *headA, struct Node* headB) {
    if (headA == NULL) return headB;
    if (headB == NULL) return headA;
    struct Node *headC = NULL;
    struct Node *tailC = NULL;

    while (headA != NULL || headB != NULL) {
        if (headB == NULL || headA->data < headB->data) {
            if (headC == NULL) {
                tailC = headC = headA;
            } else {
                tailC->prox = headA;
                tailC = headA;
            }
            headA = headA->prox;
        } else {
            if (headC == NULL) {
                tailC = headC = headB;
            } else {
                tailC->prox = headB;
                tailC = headB;
            }
            headB = headB->prox;
        }
    }
    return headC;
}