Set intersection and difference with linked lists in C

Question

I'm trying to get the intersection and difference of two sets who are each represented by a singly-linked-list of this form

struct node{
    unsigned n;
    struct node *next;
};

I already wrote this functions in the previous tasks which compute the number of elements in a list and determine if a certain element is contained in a list.

int cardinality(struct node *s){
    struct node *tmp = s;
    int count = 0;

    while(tmp != NULL){
    tmp = tmp->next;
    count++;
    }

    return count;
}

int contains(struct node *s, int v){ /* returns 0 if in list, 1 if not in list */
    struct node *tmp = s;
    int contains = 1;

    while(tmp->next != NULL){
    if(tmp->n == v){
        contains = 0;
        break;
        } else{
        if(tmp == NULL) break;
        tmp = tmp->next;
    }
    }
    return contains;
}

Now I have to code the following functions but I dont know how to do it. Should I loop through one list and for every element in the list loop through the second list to check whether it is/is not(difference) contained in the second? That seems to complex for this task, there must be an easier way to do this. Hope you can help me

void intersection(struct node *s1, struct node *s2, struct node **result){

}

void difference(struct node *s1, struct node *s2, struct node **result){

}

Answer 1

Implement these next:

// Copy one node s, giving the copy a NULL next pointer.
struct node *copy_one(struct node *s);

// Add the given node s to an existing list.
void add(struct node *s, struct node **existing);

These are useful for many purposes, but here you'll be composing them:

add(copy_one(s), &existing_list);

to build up your result.

Now the algorithm for intersection is:

set result empty
for all elements e in s1
   if e->val is contained in s2
       add a copy of e to result

For difference s1 - s2, it's

set result empty
for all elements e in s1
   if e is _not_ contained in s2
       add a copy of e to result

I will let you work out the C. There's no fun in me giving you a complete answer.

Note that the choice of linked lists to represent sets is fine for learning about C and linked lists, but not often the best choice because it leads to slow performance for big sets.