[数据结构与算法]C算法相关整理

单链表相关算法

求交集并集

//求并集
void Union(NODE l1,NODE l2){
    /**
     * 实现思路1：
     * １、将结果链表置空
     * ２、将ｌ１节点插入结果链表
     * ３、遍历ｌ２所有节点，有则跳过，无则插入
     * 
     * 实现思路2：
     * １、p1指向l1第一个节点，p2指向l2第一个节点
     * ２、比较p1和p2值，小的插入结果链表，并指针后移，直到p1或p2为空
     * ３、之后再将p1\p2不为空的那个插入
    */

    //这里是思路２的实现
    NODE p1,p2,p3;

    p1 = l1->next;
    p2 = l2->next;
    p3 = l1;

    while(p1 != NULL && p2 != NULL){

        if(p1->value <= p2->value){
            p3->next = p1;
            p3 = p1;
            p1 = p1->next;
        } else {
            p3->next = p2;
            p3 = p2;
            p2 = p2->next;
        }

    }

    p3->next = p2 ? p2 : p1;

}

//求交集
void Intersection(NODE l1,NODE l2){
    /**
     * 实现思路：
     * 同求并集思路差不多，就是相等时加入一个节点，不等时后移
    */
    NODE p1,p2,p3;
    NODE q;

    p1 = l1->next;
    p2 = l2->next;
    p3 = l1;
    p3->next = NULL;

    while(p1 != NULL && p2 != NULL){

        if(p1->value < p2->value){
            p1 = p1->next;
        } else if (p1->value > p2->value) {
            p2 = p2->next;
        } else {
            q = p2->next;
            p2->next = p3->next;
            p3->next = p2;
            p3 = p2;
            p2 = q;
        }

    }
}