给定两个链表，创建包含给定列表中元素的并集和交集的并集和交集列表。输出列表中元素的顺序并不重要。
null
例如：
Input: List1: 10 -> 15 -> 4 -> 20 List2: 8 -> 4 -> 2 -> 10 Output: Intersection List: 4 -> 10 Union List: 2 -> 8 -> 20 -> 4 -> 15 -> 10 Explanation: In this two lists 4 and 10 nodes are common. The union lists contains all the nodes of both the lists. Input: List1: 1 -> 2 -> 3 -> 4 List2: 3 -> 4 -> 8 -> 10 Output: Intersection List: 3 -> 4 Union List: 1 -> 2 -> 3 -> 4 -> 8 -> 10 Explanation: In this two lists 4 and 3 nodes are common. The union lists contains all the nodes of both the lists.
本文讨论了三种方法 邮递 实现了方法1。 在本文中，我们将看到方法2的一个实现，即使用 合并排序 .
Implementation: Following are the steps to be followed to get union and intersection lists. 1) Sort both Linked Lists using merge sort. This step takes O(mLogm) time. 2) Linearly scan both sorted lists to get the union and intersection. This step takes O(m + n) time.
算法：
- 使用合并排序对两个链表进行排序 .
- 线性扫描两个排序列表以获得并集和交集。
- 在两个链表上执行类似合并的操作，保持指向最初指向两个链表的第一个节点的指针。
- 比较两个节点，直到和，除非两个指针都不为空。
- 如果相等，则将其添加到交叉点列表和并集列表，并移动到两个指针的下一个节点
- 如果不相等，则将较小的指针值插入联合列表，并移动到下一个节点
- 如果其中一个指针为null，则遍历另一个列表及其所有节点到union list。
与方法1一样，该方法也假设列表中有不同的元素。
// C++ program to find union and intersection of // two unsorted linked lists in O(n Log n) time. #include <bits/stdc++.h> using namespace std; /* Link list node */ struct Node { int data; struct Node* next; }; /* A utility function to insert a node at the beginning of a linked list*/ void push( struct Node** head_ref, int new_data) { /* allocate node */ struct Node* new_node = ( struct Node*) malloc ( sizeof ( struct Node)); /* put in the data */ new_node->data = new_data; /* link the old list off the new node */ new_node->next = (*head_ref); /* move the head to point to the new node */ (*head_ref) = new_node; } /* UTILITY FUNCTIONS */ /* Split the nodes of the given list into front and back halves, and return the two lists using the reference parameters. If the length is odd, the extra node should go in the front list. Uses the fast/slow pointer strategy. */ void FrontBackSplit( struct Node* source, struct Node** frontRef, struct Node** backRef) { struct Node* fast; struct Node* slow; if (source == NULL || source->next == NULL) { /* length < 2 cases */ *frontRef = source; *backRef = NULL; } else { slow = source; fast = source->next; /* Advance 'fast' two nodes, and advance 'slow' one node */ while (fast != NULL) { fast = fast->next; if (fast != NULL) { slow = slow->next; fast = fast->next; } } /* 'slow' is before the midpoint in the list, so split it in two at that point. */ *frontRef = source; *backRef = slow->next; slow->next = NULL; } } /* See https:// www.geeksforgeeks.org/?p=3622 for details of this function */ struct Node* SortedMerge( struct Node* a, struct Node* b) { struct Node* result = NULL; /* Base cases */ if (a == NULL) return (b); else if (b == NULL) return (a); /* Pick either a or b, and recur */ if (a->data <= b->data) { result = a; result->next = SortedMerge(a->next, b); } else { result = b; result->next = SortedMerge(a, b->next); } return (result); } /* sorts the linked list by changing next pointers (not data) */ void mergeSort( struct Node** headRef) { struct Node* head = *headRef; struct Node *a, *b; /* Base case -- length 0 or 1 */ if ((head == NULL) || (head->next == NULL)) return ; /* Split head into 'a' and 'b' sublists */ FrontBackSplit(head, &a, &b); /* Recursively sort the sublists */ mergeSort(&a); mergeSort(&b); /* answer = merge the two sorted lists together */ *headRef = SortedMerge(a, b); } /* Function to get union of two linked lists head1 and head2 */ struct Node* getUnion( struct Node* head1, struct Node* head2) { struct Node* result = NULL; struct Node *t1 = head1, *t2 = head2; // Traverse both lists and store the // element in the resu1tant list while (t1 != NULL && t2 != NULL) { // Move to the next of first list // if its element is smaller if (t1->data < t2->data) { push(&result, t1->data); t1 = t1->next; } // Else move to the next of second list else if (t1->data > t2->data) { push(&result, t2->data); t2 = t2->next; } // If same then move to the next node // in both lists else { push(&result, t2->data); t1 = t1->next; t2 = t2->next; } } /* Print remaining elements of the lists */ while (t1 != NULL) { push(&result, t1->data); t1 = t1->next; } while (t2 != NULL) { push(&result, t2->data); t2 = t2->next; } return result; } /* Function to get intersection of two linked lists head1 and head2 */ struct Node* getIntersection( struct Node* head1, struct Node* head2) { struct Node* result = NULL; struct Node *t1 = head1, *t2 = head2; // Traverse both lists and store the same element // in the resu1tant list while (t1 != NULL && t2 != NULL) { // Move to the next of first // list if smaller if (t1->data < t2->data) t1 = t1->next; // Move to the next of second // list if it is smaller else if (t1->data > t2->data) t2 = t2->next; // If both are same else { // Store current element in the list push(&result, t2->data); // Move to the next node of both lists t1 = t1->next; t2 = t2->next; } } // return the resultant list return result; } /* A utility function to print a linked list*/ void printList( struct Node* node) { while (node != NULL) { printf ( "%d " , node->data); node = node->next; } } /* Driver program to test above function*/ int main() { /* Start with the empty list */ struct Node* head1 = NULL; struct Node* head2 = NULL; struct Node* intersection_list = NULL; struct Node* union_list = NULL; /*create a linked list 11->10->15->4->20 */ push(&head1, 20); push(&head1, 4); push(&head1, 15); push(&head1, 10); push(&head1, 11); /*create a linked list 8->4->2->10 */ push(&head2, 10); push(&head2, 2); push(&head2, 4); push(&head2, 8); /* Sort the above created Linked List */ mergeSort(&head1); mergeSort(&head2); intersection_list = getIntersection(head1, head2); union_list = getUnion(head1, head2); printf ( "First list is " ); printList(head1); printf ( "Second list is " ); printList(head2); printf ( "Intersection list is " ); printList(intersection_list); printf ( "Union list is " ); 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
复杂性分析：
- 时间复杂性： O（m logm+n logn）。 对列表进行排序所需的时间为n logn和m logm，并需要找到并集和交集的线性时间。
- 辅助空间： O（m+n）。 如果存储输出，则需要O（m+n）空间。
在下一篇文章中，将讨论方法3，即使用哈希。
本文由 萨希尔·查布拉 .如果你喜欢GeekSforgek，并想贡献自己的力量，你也可以使用 贡献极客。组织 或者把你的文章寄到contribute@geeksforgeeks.org.看到你的文章出现在Geeksforgeks主页上，并帮助其他极客。
如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写下评论。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
