CODEWITHSUNDEEP
clinked-list
Jase
Jase

Reputation: 25

Using recursion in linked list

New here. So, I was able to figure how to iterate through each element in A and compare it to one element in B. If the elements do not match, then store the element into another list, and recursively call the function to the next node in list A. The obvious problem with this is that it will compare all elements in A to only the first element in B. But I'm having difficulties on how to access the next element or node in B recursively to return a new set containing values in set A that are not in set B.

Yes, the lists are sorted.

Node *diff(Node *a, Node *b) {

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

    if ( (a == NULL) || (b == NULL) )   //Base case
            return NULL;

    if (a->val != b->val){
            tmp = a;
            tmp->next = sset_diff(a->next, b);
    }

    return tmp;


 return NULL;  //Placeholder
}

Upvotes: 2

Views: 75

Answers (2)

asaelr
asaelr

Reputation: 5456

(Especially) when using recursion, it's important to identify your sub-tasks. Here it will make sense to write another function, to check if a value is member of a list:

is_member(int val,Node *list) { //I'm assuming that it's a list of int
    if (list==NULL) return 0;
    if (list->val==val) return 1;
    return is_member(val,list->next);
}

After that, you can easily create a list of the values in A, that are not in B:

Node *diff(Node *a, Node *b) {
    if (a==NULL) return NULL; //the correct base case
    if (is_member(a->val,b)) return diff(a->next,b); //deal with one case
    Node *tmp=malloc(sizeof(Node)); //allocate it only now
    tmp->val=a->val; //assign to the value, not to the Node*
    tmp->next=diff(a->next,b); //the next elements
    return tmp;
    //there is not need to return NULL here
}

Upvotes: 1

TheQAGuy
TheQAGuy

Reputation: 494

Do you have to use recursion? This may be easier to do with a loop such as:

Node *b2;//Make this variable so you can reset b after first while loop exits
b2 = b;
while(a != NULL) {
    while(b != NULL) {
        if (a->val != b->val) {
            tmp = a;
            tmp->next = NULL;
        }
        b = b->next;
    } //End inner while loop
    a = a->next;
    b = b2;
}//End outter while loop

Upvotes: 0

Related Questions