文章目录
1 例题
2 链表合并另一种思路[参考文章,请点击](https://blog.csdn.net/weixin_39916039/article/details/80516790#commentBox)

1 例题



#include <bits/stdc++.h>

using namespace std;

typedef int ElemType;

typedef struct ListNode
{
    int val;
    ListNode *next;
    //ListNode(int x):val(x),next(NULL){}
}ListNode;

typedef struct ListNode *LinkList;

void Create(LinkList *L ,int EndTag);
int locate_elem(LinkList L ,ElemType e);
void Insert_elem(LinkList *L,int i,ElemType e);
void Delete_elem(LinkList *L,ElemType e);
void inter_sec(LinkList *A,LinkList *B);
void uni(LinkList *A,LinkList *B);
void show_afterSort(LinkList A);

int main()
{
    //freopen("1.txt","r",stdin);
    std::ios::sync_with_stdio(false);

    int end_tag;
    cin>>end_tag;

    LinkList A_;
    LinkList B_;

    Create(&A_,end_tag);
    LinkList pa=A_;
    pa=pa->next;
    cout<<"A is created as: ";
    while(pa)
    {
        cout<<pa->val<<" ";
        pa=pa->next;
    }
    cout<<endl;

    int ind;
    int ele;
    cin>>ind>>ele;
    Insert_elem(&A_,ind,ele);

    int elem;
    cin>>elem;
    Delete_elem(&A_,elem);

    int find_ele;
    cin>>find_ele;
    locate_elem(A_,find_ele);

    int not_find;
    cin>>not_find;
    locate_elem(A_,not_find);

    int end_tag2;
    cin>>end_tag2;

    Create(&B_,end_tag2);
    LinkList pb=B_;
    pb=pb->next;
    cout<<"B is created as: ";
    while(pb)
    {
        cout<<pb->val<<" ";
        pb=pb->next;
    }
    cout<<endl;

    inter_sec(&A_,&B_);
    uni(&A_,&B_);
    show_afterSort(A_);

    free(A_);
    free(B_);

    return 0;
}

/*
* 建立 带 表头结点的单线性链表L(尾插法)
* L为头结点
*/
void Create(LinkList *L ,int EndTag)
{
    LinkList p,r;

    int tmp;
    cin>>tmp;

    *L=(LinkList)malloc(sizeof(ListNode));

    r=*L;//r为指向尾部的节点

    while(tmp!=EndTag)
    {
        p=(ListNode*)malloc(sizeof(ListNode));//产生新节点
        p->val=tmp;

        /*尾插法*/
        r->next=p;
        r=p;

        cin>>tmp;
    }

    r->next=NULL;//表示当前链表结束

}


/*  寻找元素,并返回在链表中的位置
*   在指定链表L(注意没用LinkList *L,By value,非By reference)里面寻找elem
*
*/
int locate_elem(LinkList L ,ElemType e)
{
    int i=0;

    LinkList tmp;
    tmp=L->next;

    while(tmp)
    {
        i++;
        if(e==tmp->val)
            {
                cout<<e<<" is located at index of "<<i<<endl;
                return 1;
            }
        tmp=tmp->next;
    }

    cout<<e<<" is not found"<<endl;
    return 0;
}

/*
* 插入元素,向*L这个链表插入元素
* By reference,函数参数传递地址,以便在主函数里面可以修改链表
*
*/
void Insert_elem(LinkList *L,int i,ElemType e)//By reference,函数参数传递地址,以便在主函数里面可以修改链表
{
    LinkList tmp;
    tmp=*L;
    //tmp=tmp->next;//tmp这个时候是第一个元素

    int j=1;
    while(tmp&&j<i)
    {
        j++;
        tmp=tmp->next;
    }

    //tmp这个时候就是链表第i个元素,开始插入
    LinkList inse;
    inse=(LinkList)malloc(sizeof(ListNode));//产生新节点
    inse->val=e;
    inse->next=tmp->next;
    tmp->next=inse;//巨他妈呢坑

    LinkList p=*L;
    p=p->next;
    cout<<"After inserted A is ";
    while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
}


/*
** 删除链表*L中的元素,函数参数By reference
*/
void Delete_elem(LinkList *L,ElemType e)
{
    LinkList tmp;
    tmp=*L;//tmp这个时候是链表的第一个元素

    LinkList q;//用来回收被删除的节点
    while(tmp->next)
    {
        if(tmp->next->val==e)
        {
            q=tmp->next;
            tmp->next=q->next;
            free(q);//而不是free(tmp->next)
            break;
        }
        tmp=tmp->next;
    }

    LinkList p=*L;
    p=p->next;
    cout<<"After deleted A is ";
    while(p)
    {
        cout<<p->val<<" ";
        p=p->next;
    }
    cout<<endl;
}


/*
* 求交集,链表A和B,修改了链表A和B
*
*
*/
void inter_sec(LinkList *A,LinkList *B)
{
    LinkList a_tmp=*A;
    LinkList b_tmp=*B;

    a_tmp=a_tmp->next;
    //b_tmp=b_tmp->next;
    vector<int> arr;//存储交集
    while(a_tmp)
    {
        while(b_tmp->next)
        {
            if(b_tmp->next->val==a_tmp->val)
            {
                arr.push_back(a_tmp->val);
                LinkList p=b_tmp->next;
                b_tmp->next=p->next;
                free(p);
                break;
            }
            b_tmp=b_tmp->next;
        }
        a_tmp=a_tmp->next;
    }

    sort(arr.begin(),arr.end());
    cout<<"A cross B is ";
    for(int i=0;i<=arr.size()-1;i++)
        cout<<arr[i]<<" ";
    cout<<endl;
}

/*
* 求并集,
* 修改A和B, By reference
*
*/
void uni(LinkList *A,LinkList *B)
{
    LinkList a_tmp=*A;
    LinkList b_tmp=*B;
    a_tmp=a_tmp->next;
    b_tmp=b_tmp->next;

    while(a_tmp->next)//巨他妈坑
        a_tmp=a_tmp->next;

    a_tmp->next=b_tmp;

    LinkList a_tmp2=*A;
    cout<<"A union B is ";
    a_tmp2=a_tmp2->next;
    while(a_tmp2)
    {
        cout<<a_tmp2->val<<" ";
        a_tmp2=a_tmp2->next;
    }
    cout<<endl;
}

void show_afterSort(LinkList A)
{
    vector<int> arr;
    LinkList p=A->next;

    while(p)
    {
        arr.push_back(p->val);
        p=p->next;
    }

    sort(arr.begin(),arr.end());
    cout<<"A union B in sequence is ";
    for(int i=0;i<=arr.size()-1;i++)
        cout<<arr[i]<<" ";
}

2 链表合并另一种思路参考文章,请点击

目录
例题描述
解题思路
代码实现


例题描述
给定两个数组，编写一个函数来计算它们的交集。
示例1：

输入：

nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]

示例 2:

输入:

nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]


解题思路
交集即两集合共有的元素的集合。
所以首先要保证集合的唯一性，所以选择std::map容器导入元素，进行去重。
然后随意遍历其中一个集合中的元素，每个元素与另一个集合中查找这个元素：

如果存在，即为交集元素，插入需要返回的vector中。
如果不存在，即找到了map的end()位置，表示存在在A集合中的B集合中不包含的元素，那这个元素不会处理，即不放入返回的集合。


代码实现
class Solution {
public:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        vector<int> ret;
        
        set<int> s1;
        for(auto e:nums1){
           s1.insert(e);
        }
        
        set<int> s2;
        for(auto e:nums2){
           s2.insert(e);
        }
        
        for(auto e:s1){
            if(s2.find(e) != s2.end())	//s1和s2都共有此元素
                ret.push_back(e);
        }
        return ret;
    }
};

链接：https://leetcode-cn.com/problems/intersection-of-two-arrays/

例题：在二维平面上，给定两个矩形，满足矩形的每条边分别和坐标轴平行，求这个两个矩形的并的面积。即它们重叠在一起的总的面积。

解题思路：
在求两个矩形并的面积之前，我们首先需要知道其是否相交，可以按照如下方式求解：并的面积 = 总面积 - 相交面积。于是问题转变成了如何求两个矩形相交的面积。
以(x1 , y1) 和 (x2 , y2)为左下顶点和右上顶点的矩形A，和以(x1’ , y1’) 和 (x2’ , y2’)为左下顶点和右上顶点的矩形B，它们有交集的条件是：max{ x1 , x1’ } < min{ x2 , x2’ }并且max{ y1 , y1’ } < min{ y2 , y2’ }。而如果相交，它们的面积也是

area = ( min{ x2 , x2’ } - max{ x1 , x1’ } ) * ( min{ y2 , y2’ } - max{ y1 , y1’ } )。
代码示例： 51nod2488
#include<cstdio>
#include<iostream>
using namespace std;
const int N = 10;
int xx1[N],xx2[N],yy1[N],yy2[N];
typedef long long ll;
ll jiao(int a,int b){
    ll tx1 = max(xx1[a],xx1[b]),tx2 = min(xx2[a],xx2[b]);
    ll ty1 = max(yy1[a],yy1[b]),ty2 = min(yy2[a],yy2[b]);
    if( tx1 >= tx2 || ty1 >= ty2) return 0;
    return (tx2-tx1)*(ty2-ty1);
}
ll area(int x){
    return (xx2[x]-xx1[x])*(yy2[x]-yy1[x]);
}
int main(){
    scanf("%d%d%d%d",xx1+1,yy1+1,xx2+1,yy2+1);
    scanf("%d%d%d%d",xx1+2,yy1+2,xx2+2,yy2+2);
    ll ans = area(1)+area(2);
    ans -= jiao(1,2);
    printf("%lld\n",ans);
    return 0;
}