两个链表的并集和交集

2024年8月28日 | 阅读 7 分钟

创建列表的并集和交集，包含两个给定链表中存在的元素的并集和交集。输出列表中元素的排列方式无关紧要。

示例

示例-1

List1: 10->15->4->20
List2:  8->4->2->10

输出

Intersection List: 4->10
Union List: 2->8->20->4->15->10

方法 1： 简单

The basic algorithms listed below will produce intersection and union lists, respectively.
Intersection (list1, list2)
Make the result list's initial value NULL. Every entry in list1 is found by traversing list2, and if it appears in list2, it is added to the result.
Union (lists 1, 2, and 3):
Create a new list from scratch, then store the first and second list data to remove any duplicates.
and finally add it to our new list before returning the head of the list.

代码

// C++ program to find union
// and intersection of two unsorted
// linked lists
#include "bits/stdc++.h"
using namespace std;

/* Link list node */
struct Node {
	int data;
	struct Node* next;
	Node(int x)
	{
		data = x;
		next = NULL;
	}
};

/* A utility function to insert a
node at the beginning ofa linked list*/
void push(struct Node** head_ref, int new_data);

/* A utility function to check if
given data is present in a list */
bool isPresent(struct Node* head, int data);

/* Function to get union of two
linked lists head1 and head2 */
struct Node* getUnion(struct Node* head1,
					struct Node* head2)
{
	struct Node* ans = new Node(-1);
	struct Node* head = ans;
	set<int> st;
	while (head1 != NULL) {
		st.insert(head1->data);
		head1 = head1->next;
	}
	while (head2 != NULL) {
		st.insert(head2->data);
		head2 = head2->next;
	}
	for (auto it : st) {
		struct Node* t = new Node(it);
		ans->next = t;
		ans = ans->next;
	}
	head = head->next;
	return head;
}

/* 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;

	// Traverse list1 and search each element of it in
	// list2. If the element is present in list 2, then
	// insert the element to result
	while (t1 != NULL) {
		if (isPresent(head2, t1->data))
			push(&result, t1->data);
		t1 = t1->next;
	}
	return result;
}
/* 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;
}

/* A utility function to print a linked list*/
void printList(struct Node* node)
{
	while (node != NULL) {
		cout << " " << node->data;
		node = node->next;
	}
}
bool isPresent(struct Node* head, int data)
{
	struct Node* t = head;
	while (t != NULL) {
		if (t->data == data)
			return 1;
		t = t->next;
	}
	return 0;
}

/* Driver program to test above function*/
int main()
{

	/* Start with the empty list */
	struct Node* head1 = NULL;
	struct Node* head2 = NULL;
	struct Node* intersecn = NULL;
	struct Node* unin = NULL;

	/*create a linked lists 10->15->5->20 */
	push(&head1, 20);
	push(&head1, 4);
	push(&head1, 15);
	push(&head1, 10);

	/*create a linked lists 8->4->2->10 */
	push(&head2, 10);
	push(&head2, 2);
	push(&head2, 4);
	push(&head2, 8);
	intersecn = getIntersection(head1, head2);
	unin = getUnion(head1, head2);
	cout << "\n First list is " << endl;
	printList(head1);
	cout << "\n Second list is " << endl;
	printList(head2);
	cout << "\n Intersection list is " << endl;
	printList(intersecn);
	cout << "\n Union list is " << endl;
	printList(unin);
	return 0;
}

输出

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(m*n)。

其中，“m”和“n”分别指第一和第二个链表中的元素总数。

对于并集，我们检查 list-2 中的每个元素是否已存在于使用 list-1 创建的结果列表中。

对于交集，我们检查 list-1 中的每个元素是否也存在于 list-2 中。

额外空间： O (1)。

未使用任何数据结构来存储值。

方法 2： 使用归并排序

此方法中用于交集和并集的方法非常相似。在对提供的链表进行排序后，我们遍历排序后的链表以获得并集和交集。

以下是为获得交集和并集列表需要执行的操作。

使用归并排序对第一个链表进行排序。此步骤需要 O(mLogm) 时间。有关此阶段的信息，请参阅此文章。

使用归并排序对第二个链表进行排序。此步骤需要 O(nLogn) 时间。有关此阶段的信息，请参阅此文章。

使用线性搜索，找到两个排序链表的交集和并集。此步骤需要 O(m + n) 时间。用于排序数组的相同算法可用于此阶段。

此方法的总时间复杂度为 O(mLogm + nLogn)，比方法 1 的时间消耗少。

方法 3： 散列

并集 (list1, list2)

创建一个空的哈希表，并将结果列表初始化为 NULL。在遍历两个链表时，逐个检查每个元素是否在哈希表中。如果元素不存在，则将其添加到结果列表中。如果元素存在，则忽略它。

交集 (list1, list2)

创建一个空的哈希表，并将结果列表初始化为 NULL。遍历 list-1。检查 list-1 中的每个元素，并将其插入哈希表中。在遍历 list-2 时，逐个查找哈希表中的每个元素。如果元素存在于哈希表中，则将其插入结果列表中。如果元素不存在，则忽略它。

以上两种方法都假设没有重复项。

代码

// Java code for Union and Intersection of two
// Linked Lists
import java.util.HashMap;
import java.util.HashSet;

class LinkedList {
	Node head; // head of list

	/* Linked list Node*/
	class Node {
		int data;
		Node next;
		Node(int d)
		{
			data = d;
			next = null;
		}
	}

	/* Utility function to print list */
	void printList()
	{
		Node temp = head;
		while (temp != null) {
			System.out.print(temp.data + " ");
			temp = temp.next;
		}
		System.out.println();
	}

	/* Inserts a node at start of linked list */
	void push(int new_data)
	{
		/* 1 & 2: Allocate the Node &
		Put in the data*/
		Node new_node = new Node(new_data);

		/* 3. Make next of new Node as head */
		new_node.next = head;

		/* 4. Move the head to point to new Node */
		head = new_node;
	}

	public void append(int new_data)
	{
		if (this.head == null) {
			Node n = new Node(new_data);
			this.head = n;
			return;
		}
		Node n1 = this.head;
		Node n2 = new Node(new_data);
		while (n1.next != null) {
			n1 = n1.next;
		}

		n1.next = n2;
		n2.next = null;
	}

	/* A utility function that returns true if data is
	present in linked list else return false */
	boolean isPresent(Node head, int data)
	{
		Node t = head;
		while (t != null) {
			if (t.data == data)
				return true;
			t = t.next;
		}
		return false;
	}

	LinkedList getIntersection(Node head1, Node head2)
	{
		HashSet<Integer> hset = new HashSet<>();
		Node n1 = head1;
		Node n2 = head2;
		LinkedList result = new LinkedList();

		// loop stores all the elements of list1 in hset
		while (n1 != null) {
			if (hset.contains(n1.data)) {
				hset.add(n1.data);
			}
			else {
				hset.add(n1.data);
			}
			n1 = n1.next;
		}

		// For every element of list2 present in hset
		// loop inserts the element into the result
		while (n2 != null) {
			if (hset.contains(n2.data)) {
				result.push(n2.data);
			}
			n2 = n2.next;
		}
		return result;
	}

	LinkedList getUnion(Node head1, Node head2)
	{
		// HashMap that will store the
		// elements of the lists with their counts
		HashMap<Integer, Integer> hmap = new HashMap<>();
		Node n1 = head1;
		Node n2 = head2;
		LinkedList result = new LinkedList();

		// loop inserts the elements and the count of
		// that element of list1 into the hmap
		while (n1 != null) {
			if (hmap.containsKey(n1.data)) {
				int val = hmap.get(n1.data);
				hmap.put(n1.data, val + 1);
			}
			else {
				hmap.put(n1.data, 1);
			}
			n1 = n1.next;
		}

		// loop further adds the elements of list2 with
		// their counts into the hmap
		while (n2 != null) {
			if (hmap.containsKey(n2.data)) {
				int val = hmap.get(n2.data);
				hmap.put(n2.data, val + 1);
			}
			else {
				hmap.put(n2.data, 1);
			}
			n2 = n2.next;
		}

		// Eventually add all the elements
		// into the result that are present in the hmap
		for (int a : hmap.keySet()) {
			result.append(a);
		}
		return result;
	}

	/* Driver program to test above functions */
	public static void main(String args[])
	{
		LinkedList llist1 = new LinkedList();
		LinkedList llist2 = new LinkedList();
		LinkedList union = new LinkedList();
		LinkedList intersection = new LinkedList();

		/*create a linked list 10->15->4->20 */
		llist1.push(20);
		llist1.push(4);
		llist1.push(15);
		llist1.push(10);

		/*create a linked list 8->4->2->10 */
		llist2.push(10);
		llist2.push(2);
		llist2.push(4);
		llist2.push(8);

		intersection
			= intersection.getIntersection(llist1.head,
										llist2.head);
		union = union.getUnion(llist1.head, llist2.head);

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

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

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

		System.out.println("Union List is");
		union.printList();
	}
}

输出

First List is
10 15 4 20 
Second List is
8 4 2 10 
Intersection List is
10 4 
Union List is
2 4 20 8 10 15

复杂性分析

时间复杂度

时间复杂度 O(m+n)。

其中，“m”和“n”分别指第一和第二个链表中的元素总数。

并集需要遍历两个链表，将元素存储在哈希映射中，并更新每个计数。

对于交集：应遍历 list-1，将其元素存储在哈希映射中，然后检查 list-2 中的每个元素是否已存在于映射中。这需要 O(1) 的时间延迟。

对于交集，我们检查 list-1 中的每个元素是否也存在于 list-2 中。

额外空间： O (m+n)。

使用哈希映射数据结构来存储值。

下一个主题数组中的第 K 大元素

两个链表的并集和交集

示例

代码

代码

联系信息

关注我们

教程

面试题

在线编译器

Python

Java

.Net Framework

AI, ML and Data Science

Cloud Technology

B.Tech and MCA

Web Technology

PHP

Software Testing

Technical Interview

Java Interview

Python

Web Interview

Database Interview

B.Tech / MCA

Important Interview

Software Testing Interview

Company Interviews

Online Compilers

Multiple Choice Questions

数据结构教程

DS 数组

DS 链表

DS 栈

DS 队列

DS 树

DS 图

DS 搜索

DS 排序

哈希与堆

差异

二叉树

二叉搜索树

AVL 树

单向链表

双向链表

循环链表

循环双向链表

DS 选择题

其他

两个链表的并集和交集

示例

代码

代码

相关帖子

使用多项式哈希表实现动态线段树

检测并移除链表中的循环

蛇形打印矩阵

使用 RMQ 在二叉树中查找 LCA

根据给定查询查找满二叉树中着色节点的数量

反转队列

计算指定范围内的优美数字

计数排序和桶排序的区别

半结构化数据

二维二叉索引树或 Fenwick 树

订阅 Tpoint Tech

联系信息

关注我们

教程

面试题

在线编译器