Dadas dos listas doblemente enlazadas. La tarea es encontrar el número total de Nodes comunes en la lista doblemente enlazada.
Ejemplos:
Input : list 1 = 15 <=> 16 <=> 10 <=> 9 <=> 6 <=> 7 <=> 17 list 2 = 15 <=> 16 <=> 45 <=> 9 <=> 6 Output : Number of common nodes: 4 Input : list 1 = 18 <=> 30 <=> 92 <=> 46 <=> 72 <=> 1 list 2 = 12 <=> 32 <=> 45 <=> 9 <=> 6 <=> 30 Output : Number of common nodes: 1
Enfoque: recorrer ambas listas hasta el final de la lista usando dos bucles anidados. Para cada Node en la lista 1, verifique si coincide con algún Node en la lista 2. En caso afirmativo, incremente el recuento de Nodes comunes. Finalmente, imprima el conteo.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to count
// common element in given two
// doubly linked list
#include <bits/stdc++.h>
using namespace std;
// Node of the doubly linked list
struct Node {
int data;
Node *prev, *next;
};
// Function to insert a node at the beginning
// of the Doubly Linked List
void push(Node** head_ref, int new_data)
{
// allocate node
Node* new_node = (Node*)malloc(sizeof(struct Node));
// put in the data
new_node->data = new_data;
// since we are adding at the beginning,
// prev is always NULL
new_node->prev = NULL;
// link the old list off the new node
new_node->next = (*head_ref);
// change prev of head node to new node
if ((*head_ref) != NULL)
(*head_ref)->prev = new_node;
// move the head to point to the new node
(*head_ref) = new_node;
}
// Count common nodes in both list1 and list 2
int countCommonNodes(Node** head_ref, Node** head)
{
// head for list 1
Node* ptr = *head_ref;
// head for list 2
Node* ptr1 = *head;
// initialize count = 0
int count = 0;
// traverse list 1 till the end
while (ptr != NULL) {
// traverse list 2 till the end
while (ptr1 != NULL) {
// if node value is equal then
// increment count
if (ptr->data == ptr1->data) {
count++;
break;
}
// increment pointer list 2
ptr1 = ptr1->next;
}
// again list 2 start with starting point
ptr1 = *head;
// increment pointer list 1
ptr = ptr->next;
}
// return count of common nodes
return count;
}
// Driver program
int main()
{
// start with the empty list
Node* head = NULL;
Node* head1 = NULL;
// create the doubly linked list 1
// 15 <-> 16 <-> 10 <-> 9 <-> 6 <-> 7 <-> 17
push(&head, 17);
push(&head, 7);
push(&head, 6);
push(&head, 9);
push(&head, 10);
push(&head, 16);
push(&head, 15);
// create the doubly linked list 2
// 15 <-> 16 <-> 45 <-> 9 <-> 6
push(&head1, 6);
push(&head1, 9);
push(&head1, 45);
push(&head1, 16);
push(&head1, 15);
cout << "Number of common nodes:"
<< countCommonNodes(&head, &head1);
return 0;
}
Java
// Java implementation to count
// common element in given two
// doubly linked list
class GFG
{
// Node of the doubly linked list
static class Node
{
int data;
Node prev, next;
};
// Function to insert a node at the beginning
// of the Doubly Linked List
static Node push(Node head_ref, int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = head_ref;
// change prev of head node to new node
if (head_ref != null)
head_ref.prev = new_node;
// move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Count common nodes in both list1 and list 2
static int countCommonNodes(Node head_ref,
Node head)
{
// head for list 1
Node ptr = head_ref;
// head for list 2
Node ptr1 = head;
// initialize count = 0
int count = 0;
// traverse list 1 till the end
while (ptr != null)
{
// traverse list 2 till the end
while (ptr1 != null)
{
// if node value is equal then
// increment count
if (ptr.data == ptr1.data)
{
count++;
break;
}
// increment pointer list 2
ptr1 = ptr1.next;
}
// again list 2 start with starting point
ptr1 = head;
// increment pointer list 1
ptr = ptr.next;
}
// return count of common nodes
return count;
}
// Driver Code
public static void main(String[] args)
{
// start with the empty list
Node head = null;
Node head1 = null;
// create the doubly linked list 1
// 15 <. 16 <. 10 <. 9 <. 6 <. 7 <. 17
head = push(head, 17);
head = push(head, 7);
head = push(head, 6);
head = push(head, 9);
head = push(head, 10);
head = push(head, 16);
head = push(head, 15);
// create the doubly linked list 2
// 15 <. 16 <. 45 <. 9 <. 6
head1 = push(head1, 6);
head1 = push(head1, 9);
head1 = push(head1, 45);
head1 = push(head1, 16);
head1 = push(head1, 15);
System.out.println("Number of common nodes: " +
countCommonNodes(head, head1));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation to count
# common element in given two
# doubly linked list
# Node of the doubly linked list
class Node:
def __init__(self, data):
self.data = data
self.prev = None
self.next = None
# Function to insert a node at the beginning
# of the Doubly Linked List
def push(head_ref, new_data):
# allocate node
new_node = Node(new_data)
# put in the data
new_node.data = new_data;
# since we are adding at the beginning,
# prev is always None
new_node.prev = None;
# link the old list off the new node
new_node.next = (head_ref);
# change prev of head node to new node
if ((head_ref) != None):
(head_ref).prev = new_node;
# move the head to point to the new node
(head_ref) = new_node;
return head_ref
# Count common nodes in both list1 and list 2
def countCommonNodes(head_ref, head):
# head for list 1
ptr = head_ref;
# head for list 2
ptr1 = head;
# initialize count = 0
count = 0;
# traverse list 1 till the end
while (ptr != None):
# traverse list 2 till the end
while (ptr1 != None):
# if node value is equal then
# increment count
if (ptr.data == ptr1.data):
count += 1
break;
# increment pointer list 2
ptr1 = ptr1.next;
# again list 2 start with starting point
ptr1 = head;
# increment pointer list 1
ptr = ptr.next;
# return count of common nodes
return count;
# Driver program
if __name__=='__main__':
# start with the empty list
head = None;
head1 = None;
# create the doubly linked list 1
# 15 <. 16 <. 10 <. 9 <. 6 <. 7 <. 17
head = push(head, 17);
head = push(head, 7);
head = push(head, 6);
head = push(head, 9);
head = push(head, 10);
head = push(head, 16);
head = push( head, 15);
# create the doubly linked list 2
# 15 <. 16 <. 45 <. 9 <. 6
head1 = push(head1, 6);
head1 = push(head1, 9);
head1 = push(head1, 45);
head1 = push(head1, 16);
head1 = push(head1, 15);
print("Number of common nodes: " + str(countCommonNodes(head, head1)))
# This code is contributed by rutvik_56.
C#
// C# implementation to count
// common element in given two
// doubly linked list
using System;
class GFG
{
// Node of the doubly linked list
public class Node
{
public int data;
public Node prev, next;
};
// Function to insert a node at the beginning
// of the Doubly Linked List
static Node push(Node head_ref, int new_data)
{
// allocate node
Node new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = head_ref;
// change prev of head node to new node
if (head_ref != null)
head_ref.prev = new_node;
// move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Count common nodes in both list1 and list 2
static int countCommonNodes(Node head_ref,
Node head)
{
// head for list 1
Node ptr = head_ref;
// head for list 2
Node ptr1 = head;
// initialize count = 0
int count = 0;
// traverse list 1 till the end
while (ptr != null)
{
// traverse list 2 till the end
while (ptr1 != null)
{
// if node value is equal then
// increment count
if (ptr.data == ptr1.data)
{
count++;
break;
}
// increment pointer list 2
ptr1 = ptr1.next;
}
// again list 2 start with starting point
ptr1 = head;
// increment pointer list 1
ptr = ptr.next;
}
// return count of common nodes
return count;
}
// Driver Code
public static void Main(String[] args)
{
// start with the empty list
Node head = null;
Node head1 = null;
// create the doubly linked list 1
// 15 <. 16 <. 10 <. 9 <. 6 <. 7 <. 17
head = push(head, 17);
head = push(head, 7);
head = push(head, 6);
head = push(head, 9);
head = push(head, 10);
head = push(head, 16);
head = push(head, 15);
// create the doubly linked list 2
// 15 <. 16 <. 45 <. 9 <. 6
head1 = push(head1, 6);
head1 = push(head1, 9);
head1 = push(head1, 45);
head1 = push(head1, 16);
head1 = push(head1, 15);
Console.WriteLine("Number of common nodes: " +
countCommonNodes(head, head1));
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript implementation to count
// common element in given two
// doubly linked list
// Node of the doubly linked list
class Node {
constructor(val) {
this.data = val;
this.prev = null;
this.next = null;
}
}
// Function to insert a node at the beginning
// of the Doubly Linked List
function push(head_ref , new_data) {
// allocate node
var new_node = new Node();
// put in the data
new_node.data = new_data;
// since we are adding at the beginning,
// prev is always null
new_node.prev = null;
// link the old list off the new node
new_node.next = head_ref;
// change prev of head node to new node
if (head_ref != null)
head_ref.prev = new_node;
// move the head to point to the new node
head_ref = new_node;
return head_ref;
}
// Count common nodes in both list1 and list 2
function countCommonNodes(head_ref, head) {
// head for list 1
var ptr = head_ref;
// head for list 2
var ptr1 = head;
// initialize count = 0
var count = 0;
// traverse list 1 till the end
while (ptr != null) {
// traverse list 2 till the end
while (ptr1 != null) {
// if node value is equal then
// increment count
if (ptr.data == ptr1.data) {
count++;
break;
}
// increment pointer list 2
ptr1 = ptr1.next;
}
// again list 2 start with starting point
ptr1 = head;
// increment pointer list 1
ptr = ptr.next;
}
// return count of common nodes
return count;
}
// Driver Code
// start with the empty list
var head = null;
var head1 = null;
// create the doubly linked list 1
// 15 <. 16 <. 10 <. 9 <. 6 <. 7 <. 17
head = push(head, 17);
head = push(head, 7);
head = push(head, 6);
head = push(head, 9);
head = push(head, 10);
head = push(head, 16);
head = push(head, 15);
// create the doubly linked list 2
// 15 <. 16 <. 45 <. 9 <. 6
head1 = push(head1, 6);
head1 = push(head1, 9);
head1 = push(head1, 45);
head1 = push(head1, 16);
head1 = push(head1, 15);
document.write("Number of common nodes: "
+ countCommonNodes(head, head1));
// This code contributed by umadevi9616
</script>
Producción:
Number of common nodes:4