在链表中使用递归

Question

新建。所以我能图如何遍历每个元素和把它比作一个元素在B .如果不匹配的元素,然后存储到另一个列表的元素,递归地调用函数到下一个节点列表A显而易见的问题是,它只将比较所有元素中的第一个元素。但我有困难如何访问下一个元素或节点B递归返回一组新的包含值在设置不设置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);
}

之后，您可以轻松地创建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
}

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