# 两个链表的并集和相交

## 使用案列

Union_list：21→14→12→10→9→5→3

## 算法

1. 通过声明列表的开头和下一个指针来创建链接列表。
2. 使用insert func将元素插入到两个列表中。
3. 使用合并排序算法对两个链表进行排序。
4. 最后，对已排序的列表进行线性扫描，以获取列表的并集和交集。

## 实施

### 用于两个链表的并集和交集的C ++程序

```#include<iostream>
#include<stdlib.h>
using namespace std;

struct Node
{
int value;
struct Node* next;
};

void insert(struct Node** head, int new_value)
{
struct Node* NewNode = (struct Node*) malloc(sizeof(struct Node));

NewNode->value = new_value;

}

void Front_Back(struct Node* source, struct Node** front, struct Node** back)
{
struct Node* fast;
struct Node* slow;
if (source==NULL || source->next==NULL)
{
*front = source;
*back = NULL;
}
else
{
slow = source;
fast = source->next;

while (fast != NULL)
{
fast = fast->next;
if (fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
}

*front = source;
*back = slow->next;
slow->next = NULL;
}
}

struct Node* Sort_merge(struct Node* fst, struct Node* sec)
{
struct Node* result = NULL;

if (fst == NULL)
return(sec);
else if (sec==NULL)
return(fst);

if (fst->value <= sec->value)
{
result = fst;
result->next = Sort_merge(fst->next, sec);
}
else
{
result = sec;
result->next = Sort_merge(fst, sec->next);
}
return(result);
}

{
struct Node *a, *b;

return;

Sort(&a);
Sort(&b);

}

{
struct Node *result = NULL;

while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
{
insert(&result, t1->value);
t1 = t1->next;
}

else if (t1->value>t2->value)
{
insert(&result, t2->value);
t2 = t2->next;
}
else
{
insert(&result, t2->value);
t1 = t1->next;
t2 = t2->next;
}
}

while (t1 != NULL)
{
insert(&result, t1->value);
t1 = t1->next;
}
while (t2 != NULL)
{
insert(&result, t2->value);
t2 = t2->next;
}

return result;
}

{
struct Node *result = NULL;

while (t1 != NULL && t2 != NULL)
{
if (t1->value < t2->value)
t1 = t1->next;

else if (t1->value > t2->value)
t2 = t2->next;

else
{
insert(&result, t2->value);

t1 = t1->next;
t2 = t2->next;
}
}

return result;
}

void printList (struct Node *node)
{
while (node != NULL)
{
cout<<node->value << " ";
node = node->next;
}
cout<<endl;
}

int main()
{
struct Node* intersection_list = NULL;
struct Node* union_list = NULL;

cout<<"First list is \n";

cout<<"\nSecond list is \n";

cout<<"\nIntersection list is \n";
printList(intersection_list);

cout<<"\nUnion list is \n";
printList(union_list);

return 0;
}
```
```First list is
4 10 11 15 20

Second list is
2 4 8 10

Intersection list is
10 4

Union list is
20 15 11 10 8 4 2```

### 用于两个链表的并集和交集的Java程序

```class Solution1
{

class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}

void get_union(Node hd1, Node hd2)
{
Node t1 = hd1, t2 = hd2;

while (t1 != null)
{
insert(t1.data);
t1 = t1.next;
}

while (t2 != null)
{
insert(t2.data);
t2 = t2.next;
}
}

void get_intrSection(Node hd1, Node hd2)
{
Node rst = null;
Node t1 = hd1;

while (t1 != null)
{
if (is_Present(hd2, t1.data))
insert(t1.data);
t1 = t1.next;
}
}

void printList()
{
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

void insert(int new_data)
{

Node new_node = new Node(new_data);

}

{
while (t != null)
{
if (t.data == data)
return true;
t = t.next;
}
return false;
}

public static void main(String args[])
{
Solution1 llist1 = new Solution1();
Solution1 llist2 = new Solution1();
Solution1 unin = new Solution1();
Solution1 intersecn = new Solution1();

llist1.insert(20);
llist1.insert(4);
llist1.insert(15);
llist1.insert(10);

llist2.insert(10);
llist2.insert(2);
llist2.insert(4);
llist2.insert(8);

System.out.println("First List is");
llist1.printList();

System.out.println("Second List is");
llist2.printList();

System.out.println("Intersection List is");
intersecn.printList();

System.out.println("Union List is");
unin.printList();
}
}
```
```First List is
10 15 4 20
Second List is
8 4 2 10
Intersection List is
4 10
Union List is
2 8 20 4 15 10```

## 两个链表的并集和相交的复杂性分析

### 时间复杂度

O（米+ N） 哪里 “m”个 以及 “ n” 是分别存在于第一和第二列表中的元素数。

### 空间复杂度

O（米+ N） 哪里 “m”个 以及 “ n” 是分别存在于第一和第二列表中的元素数。