Dados los punteros a los Nodes principales de dos listas enlazadas. La tarea es comparar los números representados por las listas enlazadas. Los números representados por las listas pueden contener ceros a la izquierda.
- Si los números son iguales, imprima 0 .
- Si el número representado por la primera lista enlazada es mayor que imprima 1 .
- Si el número representado por la segunda lista enlazada es mayor que print -1 .
Ejemplos:
Entrada:
List1 = 2 -> 3 -> 1 -> 2 -> 4 -> NULL
List2 = 2 -> 3 -> 2 -> 4 -> 2 -> NULL
Salida: -1Entrada:
List1 = 0 -> 0 -> 1 -> 2 -> 4 -> NULL
List2 = 0 -> 0 -> 0 -> 4 -> 2 -> NULL
Salida: 1
Enfoque: dado que los números pueden contener ceros a la izquierda, primero elimine todos los ceros a la izquierda del comienzo de las listas vinculadas. Después de eso, compare sus longitudes, si las longitudes son desiguales, esto significa que uno de los números es definitivamente mayor y devuelve 1 o -1 en función de qué longitud sea mayor. De lo contrario, recorra ambas listas simultáneamente y, mientras las recorre, comparamos los dígitos en cada Node. Si en algún momento, el dígito es desigual, devuelva 1 o -1 según el valor de los dígitos. Si se llega al final de las listas vinculadas, las listas vinculadas son idénticas y, por lo tanto, devuelven 0.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
/* Structure for a linked list node */
struct Node {
int data;
struct Node* next;
};
/* A helper function to remove zeros from
the start of the linked list */
Node* removeLeadingZeros(struct Node* a)
{
if (a != NULL && a->data == 0)
return removeLeadingZeros(a->next);
else
return a;
}
/* A helper function to find the length of
linked list*/
int getSize(struct Node* a)
{
int sz = 0;
while (a != NULL) {
a = a->next;
sz++;
}
return sz;
}
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
void push(struct Node** head_ref, int new_data)
{
/* Allocate node */
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
/* Set the data */
new_node->data = new_data;
/* Link the old list after the new node */
new_node->next = (*head_ref);
/* Set the head to point to the new node */
(*head_ref) = new_node;
}
// Function to compare the numbers
// represented as linked lists
int compare(struct Node* a,
struct Node* b)
{
// Remover leading zeroes from
// the linked lists
a = removeLeadingZeros(a);
b = removeLeadingZeros(b);
int lenA = getSize(a);
int lenB = getSize(b);
if (lenA > lenB) {
/* Since the number represented by a
has a greater length, it will be greater*/
return 1;
}
else if (lenB > lenA) {
return -1;
}
/* If the lengths of two numbers are equal
we have to check their magnitudes*/
while (a != NULL && b != NULL) {
if (a->data > b->data)
return 1;
else if (a->data < b->data)
return -1;
/* If we reach here, then a and b are
not NULL and their data is same, so
move to next nodes in both lists */
a = a->next;
b = b->next;
}
// If linked lists are identical, then
// we need to return zero
return 0;
}
// Driver code
int main()
{
/* The constructed linked lists are :
a: 5->6->7
b: 2->3->3 */
struct Node* a = NULL;
push(&a, 7);
push(&a, 6);
push(&a, 5);
struct Node* b = NULL;
push(&b, 3);
push(&b, 3);
push(&b, 2);
cout << compare(a, b);
return 0;
}
Java
// Java implementation of the approach
class GFG
{
/* Structure for a linked list node */
static class Node
{
int data;
Node next;
};
/* A helper function to remove zeros from
the start of the linked list */
static Node removeLeadingZeros(Node a)
{
if (a != null && a.data == 0)
return removeLeadingZeros(a.next);
else
return a;
}
/* A helper function to find the length of
linked list*/
static int getSize(Node a)
{
int sz = 0;
while (a != null)
{
a = a.next;
sz++;
}
return sz;
}
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
static Node push(Node head_ref, int new_data)
{
/* Allocate node */
Node new_node = new Node();
/* Set the data */
new_node.data = new_data;
/* Link the old list after the new node */
new_node.next = head_ref;
/* Set the head to point to the new node */
head_ref = new_node;
return head_ref;
}
// Function to compare the numbers
// represented as linked lists
static int compare(Node a,
Node b)
{
// Remover leading zeroes from
// the linked lists
a = removeLeadingZeros(a);
b = removeLeadingZeros(b);
int lenA = getSize(a);
int lenB = getSize(b);
if (lenA > lenB)
{
/* Since the number represented by a
has a greater length, it will be greater*/
return 1;
}
else if (lenB > lenA)
{
return -1;
}
/* If the lengths of two numbers are equal
we have to check their magnitudes*/
while (a != null && b != null)
{
if (a.data > b.data)
return 1;
else if (a.data < b.data)
return -1;
/* If we reach here, then a and b are
not null and their data is same, so
move to next nodes in both lists */
a = a.next;
b = b.next;
}
// If linked lists are identical, then
// we need to return zero
return 0;
}
// Driver code
public static void main(String[] args)
{
/* The constructed linked lists are :
a: 5->6->7
b: 2->3->3 */
Node a = null;
a = push(a, 7);
a = push(a, 6);
a = push(a, 5);
Node b = null;
b = push(b, 3);
b = push(b, 3);
b = push(b, 2);
System.out.println(compare(a, b));
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 implementation of the approach ''' Structure for a linked list node ''' class Node: def __init__(self): self.data = 0 self.next = None ''' A helper function to remove zeros from the start of the linked list ''' def removeLeadingZeros(a): if (a != None and a.data == 0): return removeLeadingZeros(a.next); else: return a; ''' A helper function to find the length of linked list''' def getSize(a): sz = 0; while (a != None): a = a.next; sz += 1 return sz; ''' Given a reference (pointer to pointer) to the head of a list and an int, push a new node on the front of the list. ''' def push(head_ref, new_data): ''' Allocate node ''' new_node = Node() ''' Set the data ''' new_node.data = new_data; ''' Link the old list after the new node ''' new_node.next = (head_ref); ''' Set the head to point to the new node ''' (head_ref) = new_node; return head_ref # Function to compare the numbers # represented as linked lists def compare(a, b): # Remover leading zeroes from # the linked lists a = removeLeadingZeros(a); b = removeLeadingZeros(b); lenA = getSize(a); lenB = getSize(b); if (lenA > lenB): ''' Since the number represented by a has a greater length, it will be greater''' return 1; elif (lenB > lenA): return -1; ''' If the lengths of two numbers are equal we have to check their magnitudes''' while (a != None and b != None): if (a.data > b.data): return 1; elif (a.data < b.data): return -1; ''' If we reach here, then a and b are not None and their data is same, so move to next nodes in both lists ''' a = a.next; b = b.next; # If linked lists are identical, then # we need to return zero return 0; # Driver code if __name__=='__main__': ''' The constructed linked lists are : a: 5.6.7 b: 2.3.3 ''' a = None; a = push(a, 7); a = push(a, 6); a = push(a, 5); b = None; b = push(b, 3); b = push(b, 3); b = push(b, 2); print(compare(a, b)) # This code is contributed by rutvik_56
C#
// C# implementation of the approach
using System;
using System.Collections.Generic;
class GFG
{
/* Structure for a linked list node */
public class Node
{
public int data;
public Node next;
};
/* A helper function to remove zeros from
the start of the linked list */
static Node removeLeadingZeros(Node a)
{
if (a != null && a.data == 0)
return removeLeadingZeros(a.next);
else
return a;
}
/* A helper function to find the length of
linked list*/
static int getSize(Node a)
{
int sz = 0;
while (a != null)
{
a = a.next;
sz++;
}
return sz;
}
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
static Node push(Node head_ref, int new_data)
{
/* Allocate node */
Node new_node = new Node();
/* Set the data */
new_node.data = new_data;
/* Link the old list after the new node */
new_node.next = head_ref;
/* Set the head to point to the new node */
head_ref = new_node;
return head_ref;
}
// Function to compare the numbers
// represented as linked lists
static int compare(Node a, Node b)
{
// Remover leading zeroes from
// the linked lists
a = removeLeadingZeros(a);
b = removeLeadingZeros(b);
int lenA = getSize(a);
int lenB = getSize(b);
if (lenA > lenB)
{
/* Since the number represented by a
has a greater length, it will be greater*/
return 1;
}
else if (lenB > lenA)
{
return -1;
}
/* If the lengths of two numbers are equal
we have to check their magnitudes*/
while (a != null && b != null)
{
if (a.data > b.data)
return 1;
else if (a.data < b.data)
return -1;
/* If we reach here, then a and b are
not null and their data is same, so
move to next nodes in both lists */
a = a.next;
b = b.next;
}
// If linked lists are identical, then
// we need to return zero
return 0;
}
// Driver code
public static void Main(String[] args)
{
/* The constructed linked lists are :
a: 5->6->7
b: 2->3->3 */
Node a = null;
a = push(a, 7);
a = push(a, 6);
a = push(a, 5);
Node b = null;
b = push(b, 3);
b = push(b, 3);
b = push(b, 2);
Console.WriteLine(compare(a, b));
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation of the approach
/* Structure for a linked list node */
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
/* A helper function to remove zeros from
the start of the linked list */
function removeLeadingZeros( a)
{
if (a != null && a.data == 0)
return removeLeadingZeros(a.next);
else
return a;
}
/* A helper function to find the length of
linked list*/
function getSize( a)
{
let sz = 0;
while (a != null)
{
a = a.next;
sz++;
}
return sz;
}
/* Given a reference (pointer to pointer) to the
head of a list and an int, push a new node on the
front of the list. */
function push( head_ref, new_data)
{
/* Allocate node */
var new_node = new Node();
/* Set the data */
new_node.data = new_data;
/* Link the old list after the new node */
new_node.next = head_ref;
/* Set the head to point to the new node */
head_ref = new_node;
return head_ref;
}
// Function to compare the numbers
// represented as linked lists
function compare( a, b)
{
// Remover leading zeroes from
// the linked lists
a = removeLeadingZeros(a);
b = removeLeadingZeros(b);
let lenA = getSize(a);
let lenB = getSize(b);
if (lenA > lenB)
{
/* Since the number represented by a
has a greater length, it will be greater*/
return 1;
}
else if (lenB > lenA)
{
return -1;
}
/* If the lengths of two numbers are equal
we have to check their magnitudes*/
while (a != null && b != null)
{
if (a.data > b.data)
return 1;
else if (a.data < b.data)
return -1;
/* If we reach here, then a and b are
not null and their data is same, so
move to next nodes in both lists */
a = a.next;
b = b.next;
}
// If linked lists are identical, then
// we need to return zero
return 0;
}
// Driver Code
/* The constructed linked lists are :
a: 5->6->7
b: 2->3->3 */
var a = null;
a = push(a, 7);
a = push(a, 6);
a = push(a, 5);
var b = null;
b = push(b, 3);
b = push(b, 3);
b = push(b, 2);
document.write(compare(a, b));
</script>
Producción:
1
Complejidad de tiempo: O(max(N, M)) donde N y M son las longitudes de las listas enlazadas.
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por PrakharBansal1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA