Использование рекурсии в связанном списке

Question

Новое здесь. Итак, я смог вычислить, как перебирать каждый элемент в A и сравнивать его с одним элементом в B. Если элементы не совпадают, сохраните этот элемент в другом списке и рекурсивно вызовите функцию для следующего узла в списке A. Очевидная проблема заключается в том, что он будет сравнивать все элементы в A только с первым элементом в B. Но у меня возникают трудности с тем, как рекурсивно обращаться к следующему элементу или узлу B, чтобы возвращать новый набор, содержащий значения в set A, которые не находятся в наборе B.

Да, списки отсортированы.

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 
} 

Answer 1

(особенно) при использовании рекурсии, важно определить ваши подзадачи. Вот это будет иметь смысл написать еще одну функцию, чтобы проверить, является ли значение членом списка:

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); 
} 

После этого, вы можете легко создать список значений в А, которые не находятся в 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 
} 

Answer 2

Нужно ли использовать рекурсию? Это может быть проще сделать с помощью цикла, такие как:

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