Recursive symmetric difference between two linked list

Question

i'd like to share a problem i'm struggling with. I need to create two recursive function (with tail recursion, i'm not allowed to put multiple returns inside the body of the function) and the functions are: Calculate the intersection between two sets of numbers. Calculate the symmetric difference between two sets of number.

I've already done the function that calculate the intersection, and i will post it in the code section. How can i calculate the symmetric difference in the way i calculated the intersection? Because the symmetric difference is the opposite of the intersection, and maybe i can reuse some of the code i already written for the symmetric difference function.

Note: the two sets of numbers are saved in two linked lists and they are already sorted, and every number in a set is unique, they can't repeat.

Here is the function for the intersection (it works well with all the case):

t_nodo *intersezione_insieme(t_nodo *insieme_A, t_nodo* insieme_B)
{ 
    t_nodo *tmp;
    if (insieme_A == NULL || insieme_B == NULL) {
        tmp = NULL; 
    }
    else
    {
        while (insieme_A->info < insieme_B->info && insieme_A->succ != NULL) {
            insieme_A = insieme_A->succ;
        }
        while (insieme_A->info > insieme_B->info && insieme_B->succ != NULL) {
        insieme_B = insieme_B->succ;
        }

        tmp = (t_nodo*)malloc(sizeof(t_nodo));

        if (insieme_A->info == insieme_B->info) {
            tmp->info = insieme_A->info;   
            tmp->succ = intersezione_insieme(insieme_A->succ, insieme_B->succ);
        }
        else
        {
            tmp = intersezione_insieme(insieme_A->succ, insieme_B->succ);
        }
    }
    return tmp; 
}

What does the given code produce for: `A=6->7, B=5->7`? Also, you have a memory leak in the case that you enter the inner else clause. You're losing your malloc-ed memory. — Aviv Goll, May 10 '19 at 19:37
Also also, l don't think this is the right [definition of a tail recursion](https://stackoverflow.com/a/37010/4016231) — Aviv Goll, May 10 '19 at 20:21
Hello Aviv and thanks for the reply! What do you mean with the "A=6->7 , B=5->7"? — Porchetta17, May 10 '19 at 20:42
A is the list 6, 7. B is the list 5, 7. I expect the intersect to contain 7, but I think there's a bug.. — Aviv Goll, May 10 '19 at 20:44
I tried it and indeed the result is NULL, can you tell me why it happens? — Porchetta17, May 10 '19 at 21:23

Recursive symmetric difference between two linked list

0 Answers0