给定三个链表，找到三个链表中的所有公共元素。
null
例如：
Input : 10 15 20 25 12 10 12 13 15 10 12 15 24 25 26Output : 10 12 15 Input : 1 2 3 4 5 1 2 3 4 6 9 8 1 2 4 5 10Output : 1 2 4
方法1：（简单） 使用三个指针迭代给定的三个链表，如果有任何元素，则打印该元素。 上述解决方案的时间复杂度为O（N*N*N）
方法2：（使用合并排序） 在这种方法中，我们首先对三个列表进行排序，然后遍历排序后的列表以获得交集。 以下是获得三个列表相交的步骤： 1） 使用“合并排序”对第一个链表进行排序。这一步需要O（mLogm）时间。参考 这篇帖子 有关此步骤的详细信息。 2） 使用合并排序对第二个链表进行排序。这一步需要O（nLogn）时间。参考 这篇帖子 有关此步骤的详细信息。 3） 使用合并排序对第三个链表进行排序。这一步需要O（pLogp）时间。参考 这篇帖子 有关此步骤的详细信息。 3） 线性扫描三个排序列表以获得交点。这一步需要O（m+n+p）时间。这一步可以使用与所讨论的排序数组算法相同的算法来实现 在这里 . 该方法的时间复杂度为O（mLogm+nLogn+plogp），优于方法1的时间复杂度。
方法3：（散列） 以下是使用哈希法获得三个列表的交集所需遵循的步骤： 1） 创建一个空哈希表。遍历第一个链表，并在哈希表中将所有元素的频率标记为1。这一步需要O（m）时间。 2） 遍历第二个链表，如果哈希表中的当前元素频率为1，则将其标记为2。这一步需要O（n）时间。 3） 迭代第三个链表，如果哈希表中的当前元素频率为2，则将其标记为3。这一步需要O（p）时间。 4） 现在再次迭代第一个链表以检查元素的频率。如果哈希表中存在频率为3的元素，它将出现在三个链表的交集中。这一步需要O（m）时间。 该方法的时间复杂度为O（m+n+p），优于方法1和方法2的时间复杂度。
下面是上述想法的实施。
C++
// C++ program to find common element // in three unsorted linked list #include <bits/stdc++.h> #define max 1000000 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) { struct Node* new_node = ( struct Node *) malloc ( sizeof ( struct Node)); new_node->data = new_data; new_node->next = (*head_ref); (*head_ref) = new_node; } /* print the common element in between given three linked list*/ void Common( struct Node* head1, struct Node* head2, struct Node* head3) { // Creating empty hash table; unordered_map< int , int > hash; struct Node* p = head1; while (p != NULL) { // set frequency by 1 hash[p->data] = 1; p = p->next; } struct Node* q = head2; while (q != NULL) { // if the element is already exist in the // linked list set its frequency 2 if (hash.find(q->data) != hash.end()) hash[q->data] = 2; q = q->next; } struct Node* r = head3; while (r != NULL) { if (hash.find(r->data) != hash.end() && hash[r->data] == 2) // if the element frquancy is 2 it means // its present in both the first and second // linked list set its frquancy 3 hash[r->data] = 3; r = r->next; } for ( auto x : hash) { // if current frequency is 3 its means // element is common in all the given // linked list if (x.second == 3) cout << x.first << " " ; } } // Driver code int main() { // first list struct Node* head1 = NULL; push(&head1, 20); push(&head1, 5); push(&head1, 15); push(&head1, 10); // second list struct Node* head2 = NULL; push(&head2, 10); push(&head2, 20); push(&head2, 15); push(&head2, 8); // third list struct Node* head3 = NULL; push(&head3, 10); push(&head3, 2); push(&head3, 15); push(&head3, 20); Common(head1, head2, head3); return 0; } |
JAVA
// Java program to find common element // in three unsorted linked list import java.util.*; class GFG { static int max = 1000000 ; /* Link list node */ static class Node { int data; Node next; }; /* A utility function to insert a node at the beginning of a linked list */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } /* print the common element in between given three linked list*/ static void Common(Node head1, Node head2, Node head3) { // Creating empty hash table; HashMap<Integer, Integer> hash = new HashMap<Integer, Integer>(); Node p = head1; while (p != null ) { // set frequency by 1 hash. put(p.data, 1 ); p = p.next; } Node q = head2; while (q != null ) { // if the element is already exist in the // linked list set its frequency 2 if (hash.containsKey(q.data)) hash. put(q.data, 2 ); q = q.next; } Node r = head3; while (r != null ) { if (hash.containsKey(r.data)&& hash.get(r.data) == 2 ) // if the element frquancy is 2 it means // its present in both the first and second // linked list set its frquancy 3 hash. put(r.data, 3 ); r = r.next; } for (Map.Entry<Integer, Integer> x : hash.entrySet()) { // if current frequency is 3 its means // element is common in all the given // linked list if (x.getValue() == 3 ) System.out.println(x.getKey() + " " ); } } // Driver code public static void main(String[] args) { // first list Node head1 = null ; head1 = push(head1, 20 ); head1 = push(head1, 5 ); head1 = push(head1, 15 ); head1 = push(head1, 10 ); // second list Node head2 = null ; head2 = push(head2, 10 ); head2 = push(head2, 20 ); head2 = push(head2, 15 ); head2 = push(head2, 8 ); // third list Node head3 = null ; head3 = push(head3, 10 ); head3 = push(head3, 2 ); head3 = push(head3, 15 ); head3 = push(head3, 20 ); Common(head1, head2, head3); } } // This code is contributed by 29AjayKumar |
Python3
# Python3 program to find common element # in three unsorted linked list max = 1000000 # Link list node class Node: def __init__( self , data): self .data = data self . next = None # A utility function to insert a node at the # beginning of a linked list def push( head_ref, new_data): new_node = Node(new_data) new_node. next = head_ref head_ref = new_node return head_ref # Print the common element in between # given three linked list def Common(head1, head2, head3): # Creating empty hash table; hash = dict () p = head1 while (p ! = None ): # Set frequency by 1 hash [p.data] = 1 p = p. next q = head2 while (q ! = None ): # If the element is already exist in the # linked list set its frequency 2 if (q.data in hash ): hash [q.data] = 2 q = q. next r = head3 while (r ! = None ): if (r.data in hash ) and hash [r.data] = = 2 : # If the element frquancy is 2 it means # its present in both the first and second # linked list set its frquancy 3 hash [r.data] = 3 r = r. next for x in hash .keys(): # If current frequency is 3 its means # element is common in all the given # linked list if ( hash [x] = = 3 ): print (x, end = ' ' ) # Driver code if __name__ = = '__main__' : # First list head1 = None head1 = push(head1, 20 ) head1 = push(head1, 5 ) head1 = push(head1, 15 ) head1 = push(head1, 10 ) # Second list head2 = None head2 = push(head2, 10 ) head2 = push(head2, 20 ) head2 = push(head2, 15 ) head2 = push(head2, 8 ) # Third list head3 = None head3 = push(head3, 10 ) head3 = push(head3, 2 ) head3 = push(head3, 15 ) head3 = push(head3, 20 ) Common(head1, head2, head3) # This code is contributed by rutvik_56 |
C#
// C# program to find common element // in three unsorted linked list using System; using System.Collections.Generic; class GFG { static int max = 1000000; /* Link list node */ public class Node { public int data; public Node next; }; /* A utility function to insert a node at the beginning of a linked list */ static Node push(Node head_ref, int new_data) { Node new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } /* print the common element in between given three linked list*/ static void Common(Node head1, Node head2, Node head3) { // Creating empty hash table; Dictionary< int , int > hash = new Dictionary< int , int >(); Node p = head1; while (p != null ) { // set frequency by 1 hash.Add(p.data, 1); p = p.next; } Node q = head2; while (q != null ) { // if the element is already exist in the // linked list set its frequency 2 if (hash.ContainsKey(q.data)) hash[q.data] = 2; q = q.next; } Node r = head3; while (r != null ) { if (hash.ContainsKey(r.data)&& hash[r.data] == 2) // if the element frquancy is 2 it means // its present in both the first and // second linked list set its frquancy 3 hash[r.data] = 3; r = r.next; } foreach (KeyValuePair< int , int > x in hash) { // if current frequency is 3 its means // element is common in all the given // linked list if (x.Value == 3) Console.Write(x.Key + " " ); } } // Driver code public static void Main(String[] args) { // first list Node head1 = null ; head1 = push(head1, 20); head1 = push(head1, 5); head1 = push(head1, 15); head1 = push(head1, 10); // second list Node head2 = null ; head2 = push(head2, 10); head2 = push(head2, 20); head2 = push(head2, 15); head2 = push(head2, 8); // third list Node head3 = null ; head3 = push(head3, 10); head3 = push(head3, 2); head3 = push(head3, 15); head3 = push(head3, 20); Common(head1, head2, head3); } } // This code is contributed by Princi Singh |
Javascript
<script> // JavaScript program to find common element // in three unsorted linked list var max = 1000000; /* Link list node */ class Node { constructor() { this .data = 0; this .next = null ; } }; /* A utility function to insert a node at the beginning of a linked list */ function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = head_ref; head_ref = new_node; return head_ref; } /* print the common element in between given three linked list*/ function Common(head1, head2, head3) { // Creating empty hash table; var hash = new Map(); var p = head1; while (p != null ) { // set frequency by 1 hash.set(p.data, 1); p = p.next; } var q = head2; while (q != null ) { // if the element is already exist in the // linked list set its frequency 2 if (hash.has(q.data)) hash.set(q.data, 2); q = q.next; } var r = head3; while (r != null ) { if (hash.has(r.data)&& hash.get(r.data) == 2) // if the element frquancy is 2 it means // its present in both the first and // second linked list set its frquancy 3 hash.set(r.data, 3); r = r.next; } hash.forEach((value, key) => { // if current frequency is 3 its means // element is common in all the given // linked list if (value == 3) document.write(key + " " ); }); } // Driver code // first list var head1 = null ; head1 = push(head1, 20); head1 = push(head1, 5); head1 = push(head1, 15); head1 = push(head1, 10); // second list var head2 = null ; head2 = push(head2, 10); head2 = push(head2, 20); head2 = push(head2, 15); head2 = push(head2, 8); // third list var head3 = null ; head3 = push(head3, 10); head3 = push(head3, 2); head3 = push(head3, 15); head3 = push(head3, 20); Common(head1, head2, head3); </script> |
输出：
10 15 20
时间复杂度：O（m+n+p）
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
