How to create a function that inserts elements from two double-chained circular lists

Question

Well, I would like a hint of how I create the function that gets list1 and Lista2 and returns a third list with the elements interspersed from list 1 and 2, what would be the logic? my code is like this...

#include <stdio.h>
#include <stdlib.h>
#define true 1;
#define false 0;


typedef struct _nodo{
    int data;
    struct _nodo *next;
    struct _nodo *prev;
}nodo;


typedef struct _lista{
    nodo *head;
}lista;


lista *criaLista(){
    lista *l = (lista*)malloc(sizeof(lista));
    if (l != NULL){
        l->head = NULL;
        return l;
    }
    return NULL;
}


nodo *criaNodo(int data){
    nodo *n = (nodo*)malloc(sizeof(nodo));
    if (n != NULL){
        n->data = data;
        n->next = NULL;
        n->prev = NULL;
        return n;
    }
    return NULL;
}


int inserirFim(lista *l, int data){
    if (l != NULL){
        nodo *n = criaNodo(data);
        if (l->head == NULL){
            l->head = n;
            n->next = n->prev = n;
            return true;
        }
        else{
            nodo *last = l->head->prev;
            n->next = last->next;
            l->head->prev = n;
            n->prev = last;
            last->next = n;
            return true;
        }
    }
}


void display(lista *l){
    if (l != NULL && l->head != NULL){
        nodo *temp = l->head;
        while (temp->next != l->head){
            printf("%d ", temp->data);
            temp = temp->next;
        }
        printf("%d ", temp->data);
    }
}


lista *intersecao(lista *l, lista *l1){
    if (l != NULL && l->head != NULL && l1 != NULL && l1->head != NULL){
        lista *l2 = criaLista();
        nodo *temp = l->head;
        nodo *temp1 = l1->head;
        while (temp->next != l->head){
            while (temp1->next != l1->head){
                if (temp->data == temp1->data)
                    inserirFim(l2, temp->data);
                temp1 = temp1->next;
            }
            temp = temp->next;
            temp1 = l1->head;
        }
        if (temp->data == temp1->prev->data)
            inserirFim(l2, temp->data);
        return l2;
    }
}


int main()
{
        //desconsidera a main, era só pra testar se tava funcionando.
        // por isso ja inserir os numeros ordenados

    lista *l = criaLista();
    lista *l1 = criaLista();

    inserirFim(l, 100);
    inserirFim(l, 90);
    inserirFim(l, 80);
    inserirFim(l, 70);
    inserirFim(l, 60);
    inserirFim(l, 50);
    inserirFim(l, 40);

    inserirFim(l1, 100);
    inserirFim(l1, 70);
    inserirFim(l1, 50);
    inserirFim(l1, 40);

    lista *l3 = intersecao(l1, l);

    display(l3);

    printf("\n\n");
    system("pause");
    return 0;
}

Answer 1

We should never ignore the compiler warnings, which help us realize potential problems in the code. Starting with these we see that missing return in some functions, such as inserirFim and in the intersecao that if they do not enter us if there is no return.

Example:

int inserirFim(lista *l, int data){
    if (l != NULL){
        ...
        if (l->head == NULL){
            ...
            return true;
        }
        else{
            ...
            return true;
        }
    }
    return false; //faltava retorno aqui, se não entrar no if não tem valor de retorno!
}

As for the intersecao the problem is in the two cycles, which do not give the correct navigation, just as it does not contemplate lists of different sizes. For this you can change the function to look like this:

lista *intersecao(lista *l, lista *l1){
    if (l != NULL && l->head != NULL && l1 != NULL && l1->head != NULL){
        lista *l2 = criaLista();
        nodo *temp = l->head->next; //começa no segundo para simplificar o ciclo
        nodo *temp1 = l1->head->next; //começa no segundo para simplificar o ciclo

        //escreve os dois primeiros diretamente ja que começa no segundo
        inserirFim(l2, l->head->data);
        inserirFim(l2, l1->head->data);

        //enquanto uma das listas não chega ao fim escreve um elemento de cada
        while (temp != l->head && temp1 != l1->head){
            inserirFim(l2, temp->data);
            inserirFim(l2, temp1->data);
            temp = temp->next;
            temp1 = temp1->next;
        }

        //se a primeira lista chegou ao fim vai continuar com a segunda, caso contrario
        //vai continuar com a primeira
        if (temp == l->head) {
            temp = temp1;
            l = l1;
        }

        //continuar com os elementos da lista maior
        while (temp != l->head){
            inserirFim(l2, temp->data);
            temp = temp->next;
        }

        return l2; //retornar a nova lista
    }

    return NULL; //estava em falta também este retorno
}

Also the inserirFim can be simplified to:

int inserirFim(lista *l, int data){
    if (l == NULL) return false; //o teste de lista NULL logo aqui no topo

    nodo *n = criaNodo(data);

    if (l->head == NULL){
        l->head = n;
        n->next = n->prev = n;
    }
    else{ //sem ponteiro auxiliar last, que é basicamente l->head->prev
        n->next = l->head;
        n->prev = l->head->prev;
        l->head->prev->next = n;
        l->head->prev = n;
    }
    return true; //retorno true so uma vez
}

Example working on Ideone

As an additional note #define should not carry ; although some compilers allow it.