Using recursion in linked list

Question

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
}

What exactly do you want to do? Are the lists sorted? Also, be careful with memory allocations and pointers. You don't do what you think yo do. — asaelr
– asaelr, Commented Sep 20, 2015 at 1:42
I'm trying to return a new set containing values in set A that are not in set B. — Jase
– Jase, Commented Sep 20, 2015 at 1:50

asaelr · Accepted Answer · 2015-09-20 02:09:19Z

1

(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
}

answered Sep 20, 2015 at 2:09

asaelr

5,4581 gold badge19 silver badges22 bronze badges

Sign up to request clarification or add additional context in comments.

6 Comments

Jase Over a year ago

Thanks for your answer. Is there a way to use it without writing another function?

asaelr Over a year ago

You can check that in a loop: for (Node *t=b;t;t=t->next) if (a->val==t->val) return diff(a->next,b).

Jase Over a year ago

What if the list of b is empty?

asaelr Over a year ago

It's completely the same. (The condition of the loop will fail at the first time, so the body will not be executed) That's the beauty of choosing your base cases wisely.

Jase Over a year ago

Does this run in linear time if I include the for-loop?

|

TheQAGuy · Accepted Answer · 2015-09-20 01:48:50Z

0

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

answered Sep 20, 2015 at 1:48

TheQAGuy

4947 silver badges18 bronze badges

1 Comment

Jase Over a year ago

Not really, it's just practice for myself to use recursion.

Collectives™ on Stack Overflow

Using recursion in linked list

2 Answers 2

6 Comments

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

6 Comments

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related