Convert function from recursive to iterative

Question

Convert function from recursive to iterative

Navigation

#1 by (2 votes)

0

I have a merge function of linked lists working. However, recursion is being used and I would like to change the code and make it iterative. But I did not succeed.

Follow 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 got so far was 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.

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

c lista-encadeada

asked by anonymous 22.04.2018 / 03:57

1 answer

How to receive ajax data in a vector? Difference between AddMvc vs AddMvcCore

score 2 · Answer 1

Stacked, the calls in the code are. When unpinning, the nodes of the lists reattached. Back-to-front, in your original code, merge the list. In the call stack, the nodes to be connected, stored. Without stack concept and without 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. Her, the head and the tail, will keep on variables. Front-to-back yes, back-to-front, not the new list. The nodes of headA and headB , in each iteration, of your lists you must remove and to 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;
}