Dadas dos listas enlazadas ordenadas en orden creciente. Combínalos de tal manera que la lista de resultados esté en orden decreciente (orden inverso).
Ejemplos:
Input: a: 5->10->15->40
b: 2->3->20
Output: res: 40->20->15->10->5->3->2
Input: a: NULL
b: 2->3->20
Output: res: 20->3->2
Una solución simple es hacer lo siguiente.
1) Invertir la primera lista ‘a’ .
2) Invertir la segunda lista ‘b’ .
3) Combinar dos listas invertidas .
Otra solución simple es primero fusionar ambas listas, luego invertir la lista fusionada.
Ambas soluciones anteriores requieren dos recorridos de lista enlazada.
¿Cómo resolver sin reversa, O(1) espacio auxiliar (en el lugar) y solo un recorrido de ambas listas?
La idea es seguir el proceso de estilo de fusión. Inicializa la lista de resultados como vacía. Recorra ambas listas de principio a fin. Compare los Nodes actuales de ambas listas e inserte el menor de dos al principio de la lista de resultados.
1) Initialize result list as empty: res = NULL.
2) Let 'a' and 'b' be heads first and second lists respectively.
3) While (a != NULL and b != NULL)
a) Find the smaller of two (Current 'a' and 'b')
b) Insert the smaller value node at the front of result.
c) Move ahead in the list of smaller node.
4) If 'b' becomes NULL before 'a', insert all nodes of 'a'
into result list at the beginning.
5) If 'a' becomes NULL before 'b', insert all nodes of 'a'
into result list at the beginning.
A continuación se muestra la implementación de la solución anterior.
C++14
/* Given two sorted non-empty linked lists. Merge them in
such a way that the result list will be in reverse
order. Reversing of linked list is not allowed. Also,
extra space should be O(1) */
#include<iostream>
using namespace std;
/* Link list Node */
struct Node
{
int key;
struct Node* next;
};
// Given two non-empty linked lists 'a' and 'b'
Node* SortedMerge(Node *a, Node *b)
{
// If both lists are empty
if (a==NULL && b==NULL) return NULL;
// Initialize head of resultant list
Node *res = NULL;
// Traverse both lists while both of then
// have nodes.
while (a != NULL && b != NULL)
{
// If a's current value is smaller or equal to
// b's current value.
if (a->key <= b->key)
{
// Store next of current Node in first list
Node *temp = a->next;
// Add 'a' at the front of resultant list
a->next = res;
res = a;
// Move ahead in first list
a = temp;
}
// If a's value is greater. Below steps are similar
// to above (Only 'a' is replaced with 'b')
else
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
}
// If second list reached end, but first list has
// nodes. Add remaining nodes of first list at the
// front of result list
while (a != NULL)
{
Node *temp = a->next;
a->next = res;
res = a;
a = temp;
}
// If first list reached end, but second list has
// node. Add remaining nodes of first list at the
// front of result list
while (b != NULL)
{
Node *temp = b->next;
b->next = res;
res = b;
b = temp;
}
return res;
}
/* Function to print Nodes in a given linked list */
void printList(struct Node *Node)
{
while (Node!=NULL)
{
cout << Node->key << " ";
Node = Node->next;
}
}
/* Utility function to create a new node with
given key */
Node *newNode(int key)
{
Node *temp = new Node;
temp->key = key;
temp->next = NULL;
return temp;
}
/* Driver program to test above functions*/
int main()
{
/* Start with the empty list */
struct Node* res = NULL;
/* Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15
b: 2->3->20 */
Node *a = newNode(5);
a->next = newNode(10);
a->next->next = newNode(15);
Node *b = newNode(2);
b->next = newNode(3);
b->next->next = newNode(20);
cout << "List A before merge: \n";
printList(a);
cout << "\nList B before merge: \n";
printList(b);
/* merge 2 increasing order LLs in decreasing order */
res = SortedMerge(a, b);
cout << "\nMerged Linked List is: \n";
printList(res);
return 0;
}
Java
// Java program to merge two sorted linked list such that merged
// list is in reverse order
// Linked List Class
class LinkedList {
Node head; // head of list
static Node a, b;
/* Node Class */
static class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d) {
data = d;
next = null;
}
}
void printlist(Node node) {
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
Node sortedmerge(Node node1, Node node2) {
// if both the nodes are null
if (node1 == null && node2 == null) {
return null;
}
// resultant node
Node res = null;
// if both of them have nodes present traverse them
while (node1 != null && node2 != null) {
// Now compare both nodes current data
if (node1.data <= node2.data) {
Node temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
} else {
Node temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
}
// If second list reached end, but first list has
// nodes. Add remaining nodes of first list at the
// front of result list
while (node1 != null) {
Node temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
}
// If first list reached end, but second list has
// node. Add remaining nodes of first list at the
// front of result list
while (node2 != null) {
Node temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
return res;
}
public static void main(String[] args) {
LinkedList list = new LinkedList();
Node result = null;
/*Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15
b: 2->3->20*/
list.a = new Node(5);
list.a.next = new Node(10);
list.a.next.next = new Node(15);
list.b = new Node(2);
list.b.next = new Node(3);
list.b.next.next = new Node(20);
System.out.println("List a before merge :");
list.printlist(a);
System.out.println("");
System.out.println("List b before merge :");
list.printlist(b);
// merge two sorted linkedlist in decreasing order
result = list.sortedmerge(a, b);
System.out.println("");
System.out.println("Merged linked list : ");
list.printlist(result);
}
}
// This code has been contributed by Mayank Jaiswal
Python3
# Given two sorted non-empty linked lists. Merge them in
# such a way that the result list will be in reverse
# order. Reversing of linked list is not allowed. Also,
# extra space should be O(1)
# Node of a linked list
class Node:
def __init__(self, next = None, data = None):
self.next = next
self.data = data
# Given two non-empty linked lists 'a' and 'b'
def SortedMerge(a,b):
# If both lists are empty
if (a == None and b == None):
return None
# Initialize head of resultant list
res = None
# Traverse both lists while both of then
# have nodes.
while (a != None and b != None):
# If a's current value is smaller or equal to
# b's current value.
if (a.key <= b.key):
# Store next of current Node in first list
temp = a.next
# Add 'a' at the front of resultant list
a.next = res
res = a
# Move ahead in first list
a = temp
# If a's value is greater. Below steps are similar
# to above (Only 'a' is replaced with 'b')
else:
temp = b.next
b.next = res
res = b
b = temp
# If second list reached end, but first list has
# nodes. Add remaining nodes of first list at the
# front of result list
while (a != None):
temp = a.next
a.next = res
res = a
a = temp
# If first list reached end, but second list has
# node. Add remaining nodes of first list at the
# front of result list
while (b != None):
temp = b.next
b.next = res
res = b
b = temp
return res
# Function to print Nodes in a given linked list
def printList(Node):
while (Node != None):
print( Node.key, end = " ")
Node = Node.next
# Utility function to create a new node with
# given key
def newNode( key):
temp = Node()
temp.key = key
temp.next = None
return temp
# Driver program to test above functions
# Start with the empty list
res = None
# Let us create two sorted linked lists to test
# the above functions. Created lists shall be
# a: 5.10.15
# b: 2.3.20
a = newNode(5)
a.next = newNode(10)
a.next.next = newNode(15)
b = newNode(2)
b.next = newNode(3)
b.next.next = newNode(20)
print( "List A before merge: ")
printList(a)
print( "\nList B before merge: ")
printList(b)
# merge 2 increasing order LLs in decreasing order
res = SortedMerge(a, b)
print("\nMerged Linked List is: ")
printList(res)
# This code is contributed by Arnab Kundu
C#
// C# program to merge two sorted
// linked list such that merged
// list is in reverse order
// Linked List Class
using System;
class LinkedList
{
public Node head; // head of list
static Node a, b;
/* Node Class */
public class Node
{
public int data;
public Node next;
// Constructor to create a new node
public Node(int d)
{
data = d;
next = null;
}
}
void printlist(Node node)
{
while (node != null)
{
Console.Write(node.data + " ");
node = node.next;
}
}
Node sortedmerge(Node node1, Node node2)
{
// if both the nodes are null
if (node1 == null && node2 == null)
{
return null;
}
// resultant node
Node res = null;
// if both of them have nodes
// present traverse them
while (node1 != null && node2 != null)
{
// Now compare both nodes current data
if (node1.data <= node2.data)
{
Node temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
}
else
{
Node temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
}
// If second list reached end, but first
// list has nodes. Add remaining nodes of
// first list at the front of result list
while (node1 != null)
{
Node temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
}
// If first list reached end, but second
// list has node. Add remaining nodes of
// first list at the front of result list
while (node2 != null)
{
Node temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
return res;
}
// Driver code
public static void Main(String[] args)
{
LinkedList list = new LinkedList();
Node result = null;
/*Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15
b: 2->3->20*/
LinkedList.a = new Node(5);
LinkedList.a.next = new Node(10);
LinkedList.a.next.next = new Node(15);
LinkedList.b = new Node(2);
LinkedList.b.next = new Node(3);
LinkedList.b.next.next = new Node(20);
Console.WriteLine("List a before merge :");
list.printlist(a);
Console.WriteLine("");
Console.WriteLine("List b before merge :");
list.printlist(b);
// merge two sorted linkedlist in decreasing order
result = list.sortedmerge(a, b);
Console.WriteLine("");
Console.WriteLine("Merged linked list : ");
list.printlist(result);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// Javascript program to merge two
// sorted linked list such that merged
// list is in reverse order
// Node Class
class Node
{
constructor(d)
{
this.data = d;
this.next = null;
}
}
// Head of list
let head;
let a, b;
function printlist(node)
{
while (node != null)
{
document.write(node.data + " ");
node = node.next;
}
}
function sortedmerge(node1, node2)
{
// If both the nodes are null
if (node1 == null && node2 == null)
{
return null;
}
// Resultant node
let res = null;
// If both of them have nodes present
// traverse them
while (node1 != null && node2 != null)
{
// Now compare both nodes current data
if (node1.data <= node2.data)
{
let temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
}
else
{
let temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
}
// If second list reached end, but
// first list has nodes. Add
// remaining nodes of first
// list at the front of result list
while (node1 != null)
{
let temp = node1.next;
node1.next = res;
res = node1;
node1 = temp;
}
// If first list reached end, but
// second list has node. Add
// remaining nodes of first
// list at the front of result list
while (node2 != null)
{
let temp = node2.next;
node2.next = res;
res = node2;
node2 = temp;
}
return res;
}
// Driver code
let result = null;
/*Let us create two sorted linked lists to test
the above functions. Created lists shall be
a: 5->10->15
b: 2->3->20*/
a = new Node(5);
a.next = new Node(10);
a.next.next = new Node(15);
b = new Node(2);
b.next = new Node(3);
b.next.next = new Node(20);
document.write("List a before merge :<br>");
printlist(a);
document.write("<br>");
document.write("List b before merge :<br>");
printlist(b);
// Merge two sorted linkedlist in decreasing order
result = sortedmerge(a, b);
document.write("<br>");
document.write("Merged linked list : <br>");
printlist(result);
// This code is contributed by rag2127
</script>
Producción:
List A before merge: 5 10 15 List B before merge: 2 3 20 Merged Linked List is: 20 15 10 5 3 2
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(1)
Esta solución atraviesa ambas listas solo una vez, no requiere inversión y funciona en el lugar.
Este artículo es una contribución de Mohammed Raqeeb . Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA