两个链表求交集

In computer science, a linked list is a linear collection of data elements, whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes which together represent a sequence. In its most basic form, each node contains data and a reference (in other words, a link) to the next node in the sequence. This structure allows for efficient insertion or removal of elements from any position in the sequence during iteration. More complex variants add additional links, allowing more efficient insertion or removal of nodes at arbitrary positions.

在计算机科学中，链表是数据元素的线性集合，其顺序不是由它们在内存中的物理位置给出的。 相反，每个元素都指向下一个。 它是一种数据结构，由节点的集合组成，这些节点一起代表一个序列。 以其最基本的形式，每个节点都包含数据和对序列中下一个节点的引用(换句话说，就是链接)。 这种结构允许在迭代过程中从序列中的任何位置有效插入或删除元素。 更复杂的变体会添加其他链接，从而可以更有效地在任意位置插入或删除节点。

Union of two linked lists can be found by using merging the lists in a sorted manner.

两个链接列表的联盟可以通过合并列表的排序方式找到。

The intersection of the two lists can be found by only taking common elements while merging the two lists.

通过合并两个列表时仅采用公共元素，可以找到两个列表的交集 。

It has been assumed that the linked lists are sorted.

假定已对链表进行排序 。

Algorithm:

算法：

Union(L1,L2)

联合(L1，L2)

1) Declare node pointer output, output Tail as NULL    2) Repeat steps 3 to 9 while L1!=NULL AND L2!=NULL    3) Make a newNode and set its next = NULL    4) If L1->data < L2->data then        Set newNode->data = L1->data        Set L1 = L1->next    5) Else if L1->data > L2->data then        Set newNode->data = L2->data        L2 = L2->next    6) Else        i) Set Data = L1->data        ii) Set newNode->data = Data        iii) Repeat steps a) and b)         while L1!=NULL AND L2!=NULL AND L1->data == Data AND L2->data == Data            a) Set L1 = L1->next            b) Set L2 = L2->next    7) If output == NULL then        Set Output = outputTail = newNode    8) Else        a) Set outputTail->next = newNode        b) Set outputTail = outputTail->next     9) Repeat steps 10 to 14 while L1!=NULL    10) Make a newNode    11) Set outputTail->next = newNode    12) Set outputTail = outputTail->next    13) Set outputTail->data = L1->data    14) Set L1 = L1->next        Repeat steps 15 to 19 while L2!=NULL    15) Make a newNode    16) Set outputTail->next = newNode    17) Set outputTail = outputTail->next    18) Set outputTail->data = L2->data    19) Set L2 = L2->next        Return output

Intersection(L1,L2)

交叉路口(L1，L2)

1.	If L1 or L2 is NULL then return NULL    2.	Declare node pointers output, outputTail as null.    3.	Repeat steps 4 to 6 while L1!=NULL AND L2!=NULL    4.	If L1->data       data then        Set L1 = L1->next    5.	Else If L2->data         data then        Set L2 = L2->next    6.	Else        a)	Declare and set data = L1->data        b)	Make a newNode        c)	Set newNode->data = data and newNode->next = NULL        d)	If output == null then            i.	Set output = outputTail = newNode        e)	Else            i.	Set outputTail->next = newNode            ii.	Set outputTail = outputTail->next        f)	Repeat steps i and ii         while L1!=NULL AND L2!=NULL AND L1->data == data AND L2->data == data            i.	Set L1 = L1->next            ii.	Set L2 = L2->next

Code:

码：

#include 
    
     #include 
     
      struct node{
   	struct node*next;	int data;};struct node * Union(struct node * L1, struct node * L2){
   	struct node * output = NULL;	struct node * outTail = NULL;	while(L1&&L2){
   		struct node * newNode = (struct node *) malloc(sizeof(struct node));		newNode->next = NULL;		if(L1->data
      
       data){
   			newNode->data = L1->data;			L1 = L1->next;		}		else if(L1->data>L2->data){
   			newNode->data = L2->data;			L2 = L2->next;		}		else{
   			int data = L1->data;			newNode->data = data;			while(L1 && L2 && L1->data == data && L2->data == data){
   				L1 = L1->next;				L2 = L2->next;			}		}		if(!output)			output = outTail = newNode;		else{
   			outTail->next = newNode;			outTail = outTail->next;		}	}	while(L1){
   		outTail->next = (struct node *) malloc(sizeof(struct node));		outTail = outTail->next;		outTail->data = L1->data;		L1 = L1->next;	}	while(L2){
   		outTail->next = (struct node *) malloc(sizeof(struct node));		outTail = outTail->next;		outTail->data = L2->data;		L2 = L2->next;	}	outTail->next = NULL;	return output;}struct node * intersection(struct node * L1, struct node* L2){
   	if(L1 == NULL || L2 == NULL)		return NULL;	struct node * output = NULL;	struct node * outTail = NULL;	while(L1&&L2){
   		if(L1->data
       
        data){
   			L1 = L1->next;		}		else if(L2->data
        
         data){
   			L2 = L2->next;		}		else{
   			int data = L1->data;			struct node * newNode = (struct node *) malloc(sizeof(struct node));			newNode->data = data;			newNode->next = NULL;			if(output == NULL){
   				outTail = output = newNode;			}			else{
   				outTail->next = newNode;				outTail = outTail->next;			}			while(L1 && L2 && L1->data == data && L2->data == data){
   				L1 = L1->next;				L2 = L2->next;			}		}	}	return output;}struct node * createList(int listNum){
   	struct node * list = NULL;	struct node * list_tail = NULL;	printf("Enter elements of List %d in increasing order\n",listNum);	char ch = 'y';	do{
   		int data;		printf("Enter element : ");		scanf("%d",&data);		struct node * newNode = (struct node *) malloc(sizeof(struct node));		newNode->data = data;		newNode->next = NULL;		if(list == NULL){
   			list = list_tail = newNode;		}		else{
   			list_tail->next = newNode;			list_tail = list_tail->next;		}		printf("Would you like to insert another element [Y/N] : ");		scanf(" %c",&ch);	}while(ch == 'y' || ch == 'Y');		return list;}void print(struct node * list){
   	if(list == NULL){
   		printf("Empty List\n");		return;	}	while(list!=NULL){
   		printf("%d ",list->data);		list = list->next;	}	printf("\n");}int main() {
   	struct node * L1 = NULL;	struct node * L2 = NULL;	struct node * L3 = NULL;	struct node * L4 = NULL;	L1 = createList(1);	L2 = createList(2);	printf("List 1 : ");	print(L1);	printf("List 2 : ");	print(L2);	printf("Union : ");	L3 = Union(L1, L2);	print(L3);	printf("Intersection : ");	L4 = intersection(L1, L2);	print(L4);	return 0;}
        
       
      
     
    

Output

输出量

Enter elements of List 1 in increasing order Enter element : 1Would you like to insert another element [Y/N] : Y Enter element : 4Would you like to insert another element [Y/N] : Y Enter element : 9Would you like to insert another element [Y/N] : Y Enter element : 27 Would you like to insert another element [Y/N] : N Enter elements of List 2 in increasing order Enter element : 4Would you like to insert another element [Y/N] : Y Enter element : 9Would you like to insert another element [Y/N] : Y Enter element : 18 Would you like to insert another element [Y/N] : Y Enter element : 22 Would you like to insert another element [Y/N] : Y Enter element : 30 Would you like to insert another element [Y/N] : N List 1 : 1 4 9 27List 2 : 4 9 18 22 30Union : 1 4 9 18 22 27 30Intersection : 4 9

翻译自:

两个链表求交集