在链表中使用递归

Question

这里是新的。所以，我能够想出如何遍历 A 中的每个元素并将其与 B 中的一个元素进行比较。如果元素不匹配，则将元素存储到另一个列表中，并递归调用该函数到列表中的下一个节点A. 明显的问题是它会将 A 中的所有元素与 B 中的第一个元素进行比较。但是我在如何递归地访问 B 中的下一个元素或节点以 return 一个新的包含集合 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

一定要用递归吗？这可能更容易用循环来完成，例如：

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

Answer 2

（特别是）在使用递归时，识别您的子任务很重要。在这里编写另一个函数来检查一个值是否是列表的成员是有意义的：

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

之后，您可以轻松创建 A 中不在 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
}

在链表中使用递归

Using recursion in linked list

c

linked-list