[经典面试题]求解集合A与B的差集

【题目】

已知集合A和B的元素分别用不含头结点的单链表存储，函数difference()用于求解集合A与B的差集，并将结果保存在集合A的单链表中。

例如，若集合A={5,10,20,15,25,30}，集合B={5,15,35,25}，完成计算后A={10,20,30}。

结构体：

struct ListNode{
    int val;
    ListNode *next;
};

请完成函数void difference(ListNode** LA , ListNode* LB)

------迅雷校招

【代码一】

#include <iostream>
#include <string.h>
#include <algorithm>
using namespace std;

struct ListNode{
    int val;
    ListNode *next;
};

// 输出集合
void Display(ListNode* root){
    ListNode* p = root;
    while(p){
        cout<<p->val<<endl;
        p = p->next;
    }
}

// 求两个集合的差集保存在LA中
void Difference(ListNode** LA,ListNode* LB){
    // 容错处理
    if(*LA == NULL || LB == NULL){
        return;
    }
    ListNode *pa,*pb,*pre,*node;
    pa = *LA;
    pre = NULL;
    bool isDelete;
    // 遍历LA
    while(pa){
        pb = LB;
        isDelete = false;
        while(pb){
            // 删除pa
            if(pa->val == pb->val){
                isDelete = true;
                // 头元素
                if(pre == NULL){
                    *LA = pa->next;
                    pa = *LA;
                }//if
                else{
                    node = pa;
                    pre->next = pa->next;
                    delete node;
                    pa = pre->next;
                }
                break;
            }//if
            pb = pb->next;
        }//while
        // 如果有删除pa跳到pa->next
        if(!isDelete){
            pre = pa;
            pa = pa->next;
        }
    }//while
}

int main(){
    int arrayA[] = {5,10,20,15,25,30};
    int arrayB[] = {5,15,35,25};
    ListNode* node;
    // 集合A
    ListNode *LA = (ListNode*)malloc(sizeof(ListNode));
    LA->val = 5;
    LA->next = NULL;
    ListNode *p = LA;
    for(int i = 1;i < 6;i++){
        node  = (ListNode*)malloc(sizeof(ListNode));
        node->val = arrayA[i];
        node->next = NULL;
        p->next = node;
        p = node;
    }

    // 集合B
    ListNode *LB = (ListNode*)malloc(sizeof(ListNode));
    LB->val = 5;
    LB->next = NULL;
    p = LB;
    for(int i = 1;i < 4;i++){
        node  = (ListNode*)malloc(sizeof(ListNode));
        node->val = arrayB[i];
        node->next = NULL;
        p->next = node;
        p = node;
    }

    // 求AB差集
    Difference(&LA,LB);
    // 输出AB差集
    Display(LA);
}

【代码二】

// 求两个集合的差集保存在LA中
void Difference(ListNode** LA,ListNode* LB){
    // 容错处理
    if(*LA == NULL || LB == NULL){
        return;
    }
    ListNode *pa,*pb,*pre,*node;
    pa = *LA;
    pre = NULL;
    // 遍历LA
    while(pa){
        pb = LB;
        // 遍历直到末尾
        while(pb != NULL && pa->val != pb->val){
            pb = pb->next;
        }//while
        // pb中没有与之相同元素
        if(pb == NULL){
            pre = pa;
            pa = pa->next;
        }
        // 有相同元素
        else{
            // 头元素
            if(pre == NULL){
                *LA = pa->next;
                pa = pa->next;
            }
            else{
                node = pa;
                pre->next = pa->next;
                pa = pa->next;
                delete node;
            }//if
        }//if
    }//while
}