Dadas dos listas enlazadas, la tarea es encontrar el número de Nodes comunes en ambas listas enlazadas individualmente.
Ejemplos:
Entrada: Lista A = 3 -> 4 -> 12 -> 10 -> 17, Lista B = 10 -> 4 -> 8 -> 575 -> 34 -> 12 Salida: Número de Nodes comunes en ambas listas
= 3Entrada: Lista A = 12 -> 4 -> 65 -> 14 -> 59, Lista B = 14 -> 15 -> 23 -> 17 -> 41 -> 54 Salida: Número de Nodes comunes en ambas listas
= 1
Enfoque ingenuo: compare cada Node de la lista A con cada Node de la lista B. Si el Node es una coincidencia, incremente el conteo y devuelva el conteo después de comparar todos los Nodes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to common nodes which have
// same value node(s) both list
int countCommonNodes(struct Node* head1, struct Node* head2)
{
// list A
struct Node* current1 = head1;
// list B
struct Node* current2 = head2;
// set count = 0
int count = 0;
// traverse list A till the end of list
while (current1 != NULL) {
// traverse list B till the end of list
while (current2 != NULL) {
// if data is match then count increase
if (current1->data == current2->data)
count++;
// increase current pointer for next node
current2 = current2->next;
}
// increase current pointer of list A
current1 = current1->next;
// initialize list B starting point
current2 = head2;
}
// return count
return count;
}
/* Utility function to insert a node at the beginning */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a linked list */
void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
/* Driver program to test above functions */
int main()
{
struct Node* head1 = NULL;
struct Node* head2 = NULL;
/* Create following linked list
List A = 3 -> 4 -> 12 -> 10 -> 17
*/
push(&head1, 17);
push(&head1, 10);
push(&head1, 12);
push(&head1, 4);
push(&head1, 3);
// List B = 10 -> 4 -> 8 -> 575 -> 34 -> 12
push(&head2, 12);
push(&head2, 34);
push(&head2, 575);
push(&head2, 8);
push(&head2, 4);
push(&head2, 10);
// print list A
cout << "Given Linked List A: \n";
printList(head1);
// print list B
cout << "Given Linked List B: \n";
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
cout << "Number of common node in both list is = " << count;
return 0;
}
Java
// Java implementation of above approach
class GFG {
// Structure of a linked list node
static class Node {
int data;
Node next;
};
// Function to common nodes which have
// same value node(s) both list
static int countCommonNodes(Node head1, Node head2)
{
// list A
Node current1 = head1;
// list B
Node current2 = head2;
// set count = 0
int count = 0;
// traverse list A till the end of list
while (current1 != null) {
// traverse list B till the end of list
while (current2 != null) {
// if data is match then count increase
if (current1.data == current2.data)
count++;
// increase current pointer for next node
current2 = current2.next;
}
// increase current pointer of list A
current1 = current1.next;
// initialize list B starting point
current2 = head2;
}
// return count
return count;
}
// Utility function to insert a node at the beginning /
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;
}
// Utility function to print a linked list
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
Node head1 = null;
Node head2 = null;
// Create following linked list
// List A = 3 . 4 . 12 . 10 . 17
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// print list A
System.out.print("Given Linked List A: \n");
printList(head1);
// print list B
System.out.print("Given Linked List B: \n");
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
System.out.print("Number of common node in both list is = " + count);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of above approach
# Link list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to common nodes which have
# same value node(s) both list
def countCommonNodes(head1, head2):
# list A
current1 = head1
# list B
current2 = head2
# set count = 0
count = 0
# traverse list A till the end of list
while (current1 != None):
# traverse list B till the end of list
while (current2 != None):
# if data is match then count increase
if (current1.data == current2.data):
count = count + 1
# increase current pointer for next node
current2 = current2.next
# increase current pointer of list A
current1 = current1.next
# initialize list B starting point
current2 = head2
# return count
return count
# Utility function to insert a node at the beginning
def push(head_ref, new_data):
new_node = Node(0)
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
# Utility function to print a linked list
def printList( head):
while (head != None):
print(head.data, end = " ")
head = head.next
print("")
# Driver Code
if __name__=='__main__':
head1 = None
head2 = None
# Create following linked list
# List A = 3 . 4 . 12 . 10 . 17
head1 = push(head1, 17)
head1 = push(head1, 10)
head1 = push(head1, 12)
head1 = push(head1, 4)
head1 = push(head1, 3)
# List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12)
head2 = push(head2, 34)
head2 = push(head2, 575)
head2 = push(head2, 8)
head2 = push(head2, 4)
head2 = push(head2, 10)
# print list A
print("Given Linked List A: ")
printList(head1)
# print list B
print("Given Linked List B: ")
printList(head2)
# call function for count common node
count = countCommonNodes(head1, head2)
# print number of common node in both list
print("Number of common node in both list is = ", count)
# This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
class GFG {
// Structure of a linked list node
public class Node {
public int data;
public Node next;
};
// Function to common nodes which have
// same value node(s) both list
static int countCommonNodes(Node head1, Node head2)
{
// list A
Node current1 = head1;
// list B
Node current2 = head2;
// set count = 0
int count = 0;
// traverse list A till the end of list
while (current1 != null) {
// traverse list B till the end of list
while (current2 != null) {
// if data is match then count increase
if (current1.data == current2.data)
count++;
// increase current pointer for next node
current2 = current2.next;
}
// increase current pointer of list A
current1 = current1.next;
// initialize list B starting point
current2 = head2;
}
// return count
return count;
}
// Utility function to insert a node at the beginning /
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;
}
// Utility function to print a linked list
static void printList(Node head)
{
while (head != null) {
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
// Driver code
public static void Main(String[] args)
{
Node head1 = null;
Node head2 = null;
// Create following linked list
// List A = 3 . 4 . 12 . 10 . 17
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// print list A
Console.Write("Given Linked List A: \n");
printList(head1);
// print list B
Console.Write("Given Linked List B: \n");
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
Console.Write("Number of common node in both list is = " + count);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// Javascript implementation of above approach
// Structure of a linked list node
class Node
{
constructor(val)
{
this.data = val;
this.next = null;
}
}
// Function to common nodes which have
// same value node(s) both list
function countCommonNodes(head1, head2)
{
// List A
var current1 = head1;
// List B
var current2 = head2;
// Set count = 0
var count = 0;
// Traverse list A till the end of list
while (current1 != null)
{
// Traverse list B till the end of list
while (current2 != null)
{
// If data is match then count increase
if (current1.data == current2.data)
count++;
// Increase current pointer for next node
current2 = current2.next;
}
// Increase current pointer of list A
current1 = current1.next;
// Initialize list B starting point
current2 = head2;
}
// Return count
return count;
}
// Utility function to insert a node at the beginning
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;
}
// Utility function to print a linked list
function printList(head)
{
while (head != null)
{
document.write(head.data + " ");
head = head.next;
}
document.write("<br/>");
}
// Driver code
var head1 = null;
var head2 = null;
// Create following linked list
// List A = 3 . 4 . 12 . 10 . 17
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// Print list A
document.write("Given Linked List A: <br/>");
printList(head1);
// Print list B
document.write("Given Linked List B: <br/>");
printList(head2);
// Call function for count common node
var count = countCommonNodes(head1, head2);
// Print number of common node in both list
document.write("Number of common node in both list is = " +
count);
// This code is contributed by gauravrajput1
</script>
Producción:
Given Linked List A: 3 4 12 10 17 Given Linked List B: 10 4 8 575 34 12 Number of common node in both list is = 3
Complejidad de tiempo: O(M*N), donde M es la longitud de la lista A y N es la longitud de la lista B
Solución eficiente: inserte todos los Nodes de la lista enlazada A en unordered_set y luego verifique cada Node de la lista enlazada B en unordered_set . Si lo encuentra, incremente el conteo y devuelva el conteo al final.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// Structure of a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to common nodes which have
// same value node(s) both list
int countCommonNodes(struct Node* head1, struct Node* head2)
{
// list A
struct Node* current1 = head1;
// list B
struct Node* current2 = head2;
// set count = 0
int count = 0;
// create unordered_set
unordered_set<int> map;
// traverse list A till the end of list
while (current1 != NULL) {
// insert list data in map
map.insert(current1->data);
// increase current pointer of list A
current1 = current1->next;
}
while (current2 != NULL) {
// traverse list B till the end of list
// if data match then increase count
if (map.find(current2->data) != map.end())
count++;
// increase current pointer of list B
current2 = current2->next;
}
// return count
return count;
}
/* Utility function to insert a node at the beginning */
void push(struct Node** head_ref, int new_data)
{
struct Node* new_node = new Node;
new_node->data = new_data;
new_node->next = *head_ref;
*head_ref = new_node;
}
/* Utility function to print a linked list */
void printList(struct Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
cout << endl;
}
/* Driver program to test above functions */
int main()
{
struct Node* head1 = NULL;
struct Node* head2 = NULL;
/* Create following linked list
List A = 3 -> 4 -> 12 -> 10 -> 17
*/
push(&head1, 17);
push(&head1, 10);
push(&head1, 12);
push(&head1, 4);
push(&head1, 3);
// List B = 10 -> 4 -> 8 -> 575 -> 34 -> 12
push(&head2, 12);
push(&head2, 34);
push(&head2, 575);
push(&head2, 8);
push(&head2, 4);
push(&head2, 10);
// print list A
cout << "Given Linked List A: \n";
printList(head1);
// print list B
cout << "Given Linked List B: \n";
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
cout << "Number of common node in both list is = " << count;
return 0;
}
Java
// Java implementation of above approach
import java.util.*;
class solution {
// static class of a linked list node
static class Node {
int data;
Node next;
}
// Function to common nodes which have
// same value node(s) both list
static int countCommonNodes(Node head1, Node head2)
{
// list A
Node current1 = head1;
// list B
Node current2 = head2;
// set count = 0
int count = 0;
// create vector
Vector<Integer> map = new Vector<Integer>();
// traverse list A till the end of list
while (current1 != null) {
// insert list data in map
map.add(current1.data);
// increase current pointer of list A
current1 = current1.next;
}
while (current2 != null) {
// traverse list B till the end of list
// if data match then increase count
if (map.contains(current2.data))
count++;
// increase current pointer of list B
current2 = current2.next;
}
// return count
return count;
}
/* Utility function to insert a node at the beginning */
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;
}
/* Utility function to print a linked list */
static void printList(Node head)
{
while (head != null) {
System.out.print(head.data + " ");
head = head.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
Node head1 = null;
Node head2 = null;
/* Create following linked list
List A = 3 . 4 . 12 . 10 . 17
*/
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// print list A
System.out.print("Given Linked List A: \n");
printList(head1);
// print list B
System.out.print("Given Linked List B: \n");
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
System.out.print("Number of common node in both list is = " + count);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach
# Structure of a linked list node
class Node:
def __init__(self):
self.data = 0
self.next = None
# Function to common nodes which have
# same value node(s) both list
def countCommonNodes(head1, head2):
# List A
current1 = head1
# List B
current2 = head2
# Set count = 0
count = 0
# Create unordered_set
map_=set()
# Traverse list A till the end of list
while (current1 != None) :
# Add list data in map_
map_.add(current1.data)
# Increase current pointer of list A
current1 = current1.next
while (current2 != None) :
# Traverse list B till the end of list
# if data match then increase count
if ((current2.data) in map_):
count = count + 1
# Increase current pointer of list B
current2 = current2.next
# Return count
return count
# Utility function to add a node at the beginning
def push(head_ref,new_data):
new_node = Node()
new_node.data = new_data
new_node.next = head_ref
head_ref = new_node
return head_ref
# Utility function to print a linked list
def printList(head):
while (head != None) :
print(head.data, end = " ")
head = head.next
# Driver program to test above functions
head1 = None
head2 = None
# Create following linked list
# List A = 3 . 4 . 12 . 10 . 17
head1 = push(head1, 17)
head1 = push(head1, 10)
head1 = push(head1, 12)
head1 = push(head1, 4)
head1 = push(head1, 3)
# List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12)
head2 = push(head2, 34)
head2 = push(head2, 575)
head2 = push(head2, 8)
head2 = push(head2, 4)
head2 = push(head2, 10)
# Print list A
print("Given Linked List A: ")
printList(head1)
# Print list B
print( "\nGiven Linked List B: ")
printList(head2)
# Call function for count common node
count = countCommonNodes(head1, head2)
# Print number of common node in both list
print("\nNumber of common node in both list is = " , count)
# This code is contributed by Arnab Kundu
C#
// C# implementation of above approach
using System;
using System.Collections.Generic;
class GFG
{
// static class of a linked list node
public class Node
{
public int data;
public Node next;
}
// Function to common nodes which have
// same value node(s) both list
static int countCommonNodes(Node head1, Node head2)
{
// list A
Node current1 = head1;
// list B
Node current2 = head2;
// set count = 0
int count = 0;
// create vector
List<int> map = new List<int>();
// traverse list A till the end of list
while (current1 != null)
{
// insert list data in map
map.Add(current1.data);
// increase current pointer of list A
current1 = current1.next;
}
while (current2 != null)
{
// traverse list B till the end of list
// if data match then increase count
if (map.Contains(current2.data))
count++;
// increase current pointer of list B
current2 = current2.next;
}
// return count
return count;
}
/* Utility function to insert a node at the beginning */
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;
}
/* Utility function to print a linked list */
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
Console.WriteLine();
}
/* Driver code */
public static void Main(String []args)
{
Node head1 = null;
Node head2 = null;
/* Create following linked list
List A = 3 . 4 . 12 . 10 . 17
*/
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// print list A
Console.Write("Given Linked List A: \n");
printList(head1);
// print list B
Console.Write("Given Linked List B: \n");
printList(head2);
// call function for count common node
int count = countCommonNodes(head1, head2);
// print number of common node in both list
Console.Write("Number of common node in both list is = " + count);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of above approach
// static class of a linked list node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to common nodes which have
// same value node(s) both list
function countCommonNodes(head1, head2) {
// list A
var current1 = head1;
// list B
var current2 = head2;
// set count = 0
var count = 0;
// create vector
var map = [];
// traverse list A till the end of list
while (current1 != null) {
// insert list data in map
map.push(current1.data);
// increase current pointer of list A
current1 = current1.next;
}
while (current2 != null) {
// traverse list B till the end of list
// if data match then increase count
if (map.includes(current2.data)) count++;
// increase current pointer of list B
current2 = current2.next;
}
// return count
return count;
}
/* Utility function to insert a node at the beginning */
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;
}
/* Utility function to print a linked list */
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
document.write("<br>");
}
/* Driver code */
var head1 = null;
var head2 = null;
/* Create following linked list
List A = 3 . 4 . 12 . 10 . 17
*/
head1 = push(head1, 17);
head1 = push(head1, 10);
head1 = push(head1, 12);
head1 = push(head1, 4);
head1 = push(head1, 3);
// List B = 10 . 4 . 8 . 575 . 34 . 12
head2 = push(head2, 12);
head2 = push(head2, 34);
head2 = push(head2, 575);
head2 = push(head2, 8);
head2 = push(head2, 4);
head2 = push(head2, 10);
// print list A
document.write("Given Linked List A: <br>");
printList(head1);
// print list B
document.write("Given Linked List B: <br>");
printList(head2);
// call function for count common node
var count = countCommonNodes(head1, head2);
// print number of common node in both list
document.write("Number of common node in both list is = " + count);
// This code is contributed by rdtank.
</script>
Producción:
Given Linked List A: 3 4 12 10 17 Given Linked List B: 10 4 8 575 34 12 Number of common node in both list is = 3
Complejidad temporal: O(N)
Complejidad espacial: O(N)
Publicación traducida automáticamente
Artículo escrito por Amal Kumar Choubey y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA