Dadas dos listas enlazadas individuales de datos enteros. La tarea es escribir un programa que verifique de manera eficiente si dos listas enlazadas son permutaciones entre sí.
Ejemplos :
Input: 1 -> 2 -> 3 -> 4 -> 5
2 -> 1 -> 3 -> 5 -> 4
Output: Yes
Input: 10 -> 20 -> 30 -> 40
20 -> 50 -> 60 -> 70
Output: No
Enfoque: Haga lo siguiente para ambas listas enlazadas:
- Tome un Node temporal que apunte al encabezado de la lista enlazada.
- Comience a recorrer la lista enlazada y mantenga la suma y las multiplicaciones de los datos de los Nodes.
Nota: Después de tener la suma y la multiplicación de ambas listas vinculadas, verifique si la suma y la multiplicación de ambas listas vinculadas son iguales. Si son iguales, significa que las listas enlazadas son permutaciones entre sí, de lo contrario no.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program to check if linked lists
// are permutations of each other
#include <bits/stdc++.h>
using namespace std;
// A linked list node
struct Node {
int data;
struct Node* next;
};
/*Function to check if two linked lists
* are permutations of each other
* first : reference to head of first linked list
* second : reference to head of second linked list
*/
bool isPermutation(struct Node* first, struct Node* second)
{
// Variables to keep track of sum and multiplication
int sum1 = 0, sum2 = 0, mul1 = 1, mul2 = 1;
struct Node* temp1 = first;
// Traversing through linked list
// and calculating sum and multiply
while (temp1 != NULL) {
sum1 += temp1->data;
mul1 *= temp1->data;
temp1 = temp1->next;
}
struct Node* temp2 = second;
// Traversing through linked list
// and calculating sum and multiply
while (temp2 != NULL) {
sum2 += temp2->data;
mul2 *= temp2->data;
temp2 = temp2->next;
}
return ((sum1 == sum2) && (mul1 == mul2));
}
// Function to add a node at the
// beginning of 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;
}
// Driver program to test above function
int main()
{
struct Node* first = NULL;
/* First constructed linked list is:
12 -> 35 -> 1 -> 10 -> 34 -> 1 */
push(&first, 1);
push(&first, 34);
push(&first, 10);
push(&first, 1);
push(&first, 35);
push(&first, 12);
struct Node* second = NULL;
/* Second constructed linked list is:
35 -> 1 -> 12 -> 1 -> 10 -> 34 */
push(&second, 35);
push(&second, 1);
push(&second, 12);
push(&second, 1);
push(&second, 10);
push(&second, 34);
if (isPermutation(first, second)) {
cout << "Yes" << endl;
}
else {
cout << "No" << endl;
}
return 0;
}
Java
// Java program to check if linked lists
// are permutations of each other
import java.util.*;
class GFG
{
static class Node
{
int data;
Node next;
};
/*Function to check if two linked lists
* are permutations of each other
* first : reference to head of first linked list
* second : reference to head of second linked list
*/
static boolean isPermutation(Node first,
Node second)
{
// Variables to keep track of
// sum and multiplication
int sum1 = 0, sum2 = 0,
mul1 = 1, mul2 = 1;
Node temp1 = first;
// Traversing through linked list
// and calculating sum and multiply
while (temp1 != null)
{
sum1 += temp1.data;
mul1 *= temp1.data;
temp1 = temp1.next;
}
Node temp2 = second;
// Traversing through linked list
// and calculating sum and multiply
while (temp2 != null)
{
sum2 += temp2.data;
mul2 *= temp2.data;
temp2 = temp2.next;
}
return ((sum1 == sum2) &&
(mul1 == mul2));
}
// Function to add a node at the
// beginning of 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;
/* 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;
return head_ref;
}
// Driver Code
public static void main(String[] args)
{
Node first = null;
/* First constructed linked list is:
12 . 35 . 1 . 10 . 34 . 1 */
first = push(first, 1);
first = push(first, 34);
first = push(first, 10);
first = push(first, 1);
first = push(first, 35);
first = push(first, 12);
Node second = null;
/* Second constructed linked list is:
35 . 1 . 12 . 1 . 10 . 34 */
second = push(second, 35);
second = push(second, 1);
second = push(second, 12);
second = push(second, 1);
second = push(second, 10);
second = push(second, 34);
if (isPermutation(first, second))
{
System.out.print("Yes");
}
else
{
System.out.print("No");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to check if linked lists
# are permutations of each other
class Node:
def __init__(self):
self.data = 0
self.next = None
# Function to check if two linked lists
# are permutations of each other
# first : reference to head of first linked list
# second : reference to head of second linked list
def isPermutation(first, second):
# Variables to keep track of
# sum and multiplication
sum1 = 0
sum2 = 0
mul1 = 1
mul2 = 1
temp1 = first
# Traversing through linked list
# and calculating sum and multiply
while (temp1 != None):
sum1 += temp1.data
mul1 *= temp1.data
temp1 = temp1.next
temp2 = second
# Traversing through linked list
# and calculating sum and multiply
while (temp2 != None):
sum2 += temp2.data
mul2 *= temp2.data
temp2 = temp2.next
return ((sum1 == sum2) and (mul1 == mul2))
# Function to add a node at the
# beginning of Linked List
def push(head_ref, new_data):
# Allocate node
new_node = 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
return head_ref
# Driver Code
if __name__=='__main__':
first = None
# First constructed linked list is:
# 12 . 35 . 1 . 10 . 34 . 1
first = push(first, 1)
first = push(first, 34)
first = push(first, 10)
first = push(first, 1)
first = push(first, 35)
first = push(first, 12)
second = None
# Second constructed linked list is:
# 35 . 1 . 12 . 1 . 10 . 34
second = push(second, 35)
second = push(second, 1)
second = push(second, 12)
second = push(second, 1)
second = push(second, 10)
second = push(second, 34)
if (isPermutation(first, second)):
print("Yes")
else:
print("No")
# This code is contributed by pratham76
C#
// C# program to check if linked lists
// are permutations of each other
using System;
class GFG
{
public class Node
{
public int data;
public Node next;
};
/*Function to check if two linked lists
* are permutations of each other
* first : reference to head of first linked list
* second : reference to head of second linked list
*/
static bool isPermutation(Node first,
Node second)
{
// Variables to keep track of
// sum and multiplication
int sum1 = 0, sum2 = 0,
mul1 = 1, mul2 = 1;
Node temp1 = first;
// Traversing through linked list
// and calculating sum and multiply
while (temp1 != null)
{
sum1 += temp1.data;
mul1 *= temp1.data;
temp1 = temp1.next;
}
Node temp2 = second;
// Traversing through linked list
// and calculating sum and multiply
while (temp2 != null)
{
sum2 += temp2.data;
mul2 *= temp2.data;
temp2 = temp2.next;
}
return ((sum1 == sum2) &&
(mul1 == mul2));
}
// Function to add a node at the
// beginning of 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;
/* 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;
return head_ref;
}
// Driver Code
public static void Main(String[] args)
{
Node first = null;
/* First constructed linked list is:
12 . 35 . 1 . 10 . 34 . 1 */
first = push(first, 1);
first = push(first, 34);
first = push(first, 10);
first = push(first, 1);
first = push(first, 35);
first = push(first, 12);
Node second = null;
/* Second constructed linked list is:
35 . 1 . 12 . 1 . 10 . 34 */
second = push(second, 35);
second = push(second, 1);
second = push(second, 12);
second = push(second, 1);
second = push(second, 10);
second = push(second, 34);
if (isPermutation(first, second))
{
Console.Write("Yes");
}
else
{
Console.Write("No");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// JavaScript program to check if linked lists
// are permutations of each other
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/*Function to check if two linked lists
* are permutations of each other
* first : reference to head of first linked list
* second : reference to head of second linked list
*/
function isPermutation(first, second) {
// Variables to keep track of
// sum and multiplication
var sum1 = 0,
sum2 = 0,
mul1 = 1,
mul2 = 1;
var temp1 = first;
// Traversing through linked list
// and calculating sum and multiply
while (temp1 != null) {
sum1 += temp1.data;
mul1 *= temp1.data;
temp1 = temp1.next;
}
var temp2 = second;
// Traversing through linked list
// and calculating sum and multiply
while (temp2 != null) {
sum2 += temp2.data;
mul2 *= temp2.data;
temp2 = temp2.next;
}
return sum1 == sum2 && mul1 == mul2;
}
// Function to add a node at the
// beginning of Linked List
function push(head_ref, new_data) {
/* allocate node */
var new_node = new 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;
return head_ref;
}
// Driver Code
var first = null;
/* First constructed linked list is:
12 . 35 . 1 . 10 . 34 . 1 */
first = push(first, 1);
first = push(first, 34);
first = push(first, 10);
first = push(first, 1);
first = push(first, 35);
first = push(first, 12);
var second = null;
/* Second constructed linked list is:
35 . 1 . 12 . 1 . 10 . 34 */
second = push(second, 35);
second = push(second, 1);
second = push(second, 12);
second = push(second, 1);
second = push(second, 10);
second = push(second, 34);
if (isPermutation(first, second)) {
document.write("Yes");
} else {
document.write("No");
}
</script>
Producción:
Yes