Dadas dos listas enlazadas no ordenadas , la tarea es fusionarlas para obtener una lista enlazada individual ordenada .
Ejemplos:
Entrada: Lista 1 = 3 -> 1 -> 5, Lista 2 = 6-> 2 -> 4
Salida: 1 -> 2 -> 3 -> 4 -> 5 -> 6Entrada: Lista 1 = 4 -> 7 -> 5, Lista 2 = 2-> 1 -> 8 -> 1
Salida: 1 -> 1 -> 2 -> 4 -> 5 -> 7 -> 8
Enfoque ingenuo: el enfoque ingenuo es ordenar las listas vinculadas dadas y luego fusionar las dos listas vinculadas ordenadas en una sola lista en orden creciente.
Para resolver el problema mencionado anteriormente, el método ingenuo es ordenar las dos listas vinculadas individualmente y fusionar las dos listas vinculadas en una sola lista que está en orden creciente.
Enfoque eficiente: para optimizar el método anterior, concatenaremos las dos listas vinculadas y luego las ordenaremos usando cualquier algoritmo de clasificación. A continuación se muestran los pasos:
- Concatene las dos listas atravesando la primera lista hasta que lleguemos a su Node final y luego apunte el siguiente Node final al Node principal de la segunda lista. Almacene esta lista concatenada en la primera lista.
- Ordene la lista vinculada combinada anteriormente. Aquí, usaremos una ordenación de burbuja. Entonces, si el Node->siguiente->datos es menor que el Node->datos, entonces intercambie los datos de los dos Nodes adyacentes.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Create structure for a node
struct node {
int data;
node* next;
};
// Function to print the linked list
void setData(node* head)
{
node* tmp;
// Store the head of the linked
// list into a temporary node*
// and iterate
tmp = head;
while (tmp != NULL) {
cout << tmp->data
<< " -> ";
tmp = tmp->next;
}
}
// Function takes the head of the
// LinkedList and the data as
// argument and if no LinkedList
// exists, it creates one with the
// head pointing to first node.
// If it exists already, it appends
// given node at end of the last node
node* getData(node* head, int num)
{
// Create a new node
node* temp = new node;
node* tail = head;
// Insert data into the temporary
// node and point it's next to NULL
temp->data = num;
temp->next = NULL;
// Check if head is null, create a
// linked list with temp as head
// and tail of the list
if (head == NULL) {
head = temp;
tail = temp;
}
// Else insert the temporary node
// after the tail of the existing
// node and make the temporary node
// as the tail of the linked list
else {
while (tail != NULL) {
if (tail->next == NULL) {
tail->next = temp;
tail = tail->next;
}
tail = tail->next;
}
}
// Return the list
return head;
}
// Function to concatenate the two lists
node* mergelists(node** head1,
node** head2)
{
node* tail = *head1;
// Iterate through the head1 to find the
// last node join the next of last node
// of head1 to the 1st node of head2
while (tail != NULL) {
if (tail->next == NULL
&& head2 != NULL) {
tail->next = *head2;
break;
}
tail = tail->next;
}
// return the concatenated lists as a
// single list - head1
return *head1;
}
// Sort the linked list using bubble sort
void sortlist(node** head1)
{
node* curr = *head1;
node* temp = *head1;
// Compares two adjacent elements
// and swaps if the first element
// is greater than the other one.
while (curr->next != NULL) {
temp = curr->next;
while (temp != NULL) {
if (temp->data < curr->data) {
int t = temp->data;
temp->data = curr->data;
curr->data = t;
}
temp = temp->next;
}
curr = curr->next;
}
}
// Driver Code
int main()
{
node* head1 = new node;
node* head2 = new node;
head1 = NULL;
head2 = NULL;
// Given Linked List 1
head1 = getData(head1, 4);
head1 = getData(head1, 7);
head1 = getData(head1, 5);
// Given Linked List 2
head2 = getData(head2, 2);
head2 = getData(head2, 1);
head2 = getData(head2, 8);
head2 = getData(head2, 1);
// Merge the two lists
// in a single list
head1 = mergelists(&head1,
&head2);
// Sort the unsorted merged list
sortlist(&head1);
// Print the final
// sorted merged list
setData(head1);
return 0;
}
Java
// Java program for
// the above approach
class GFG{
static node head1 = null;
static node head2 = null;
// Create structure for a node
static class node
{
int data;
node next;
};
// Function to print
// the linked list
static void setData(node head)
{
node tmp;
// Store the head of the linked
// list into a temporary node
// and iterate
tmp = head;
while (tmp != null)
{
System.out.print(tmp.data + " -> ");
tmp = tmp.next;
}
}
// Function takes the head of the
// LinkedList and the data as
// argument and if no LinkedList
// exists, it creates one with the
// head pointing to first node.
// If it exists already, it appends
// given node at end of the last node
static node getData(node head, int num)
{
// Create a new node
node temp = new node();
node tail = head;
// Insert data into the temporary
// node and point it's next to null
temp.data = num;
temp.next = null;
// Check if head is null, create a
// linked list with temp as head
// and tail of the list
if (head == null)
{
head = temp;
tail = temp;
}
// Else insert the temporary node
// after the tail of the existing
// node and make the temporary node
// as the tail of the linked list
else
{
while (tail != null)
{
if (tail.next == null)
{
tail.next = temp;
tail = tail.next;
}
tail = tail.next;
}
}
// Return the list
return head;
}
// Function to concatenate
// the two lists
static node mergelists()
{
node tail = head1;
// Iterate through the
// head1 to find the
// last node join the
// next of last node
// of head1 to the
// 1st node of head2
while (tail != null)
{
if (tail.next == null &&
head2 != null)
{
tail.next = head2;
break;
}
tail = tail.next;
}
// return the concatenated
// lists as a single list - head1
return head1;
}
// Sort the linked list
// using bubble sort
static void sortlist()
{
node curr = head1;
node temp = head1;
// Compares two adjacent elements
// and swaps if the first element
// is greater than the other one.
while (curr.next != null)
{
temp = curr.next;
while (temp != null)
{
if (temp.data < curr.data)
{
int t = temp.data;
temp.data = curr.data;
curr.data = t;
}
temp = temp.next;
}
curr = curr.next;
}
}
// Driver Code
public static void main(String[] args)
{
// Given Linked List 1
head1 = getData(head1, 4);
head1 = getData(head1, 7);
head1 = getData(head1, 5);
// Given Linked List 2
head2 = getData(head2, 2);
head2 = getData(head2, 1);
head2 = getData(head2, 8);
head2 = getData(head2, 1);
// Merge the two lists
// in a single list
head1 = mergelists();
// Sort the unsorted merged list
sortlist();
// Print the final
// sorted merged list
setData(head1);
}
}
// This code is contributed by shikhasingrajput
Python3
# Python3 program for the # above approach # Create structure for a node class node: def __init__(self, x): self.data = x self.next = None # Function to print the linked # list def setData(head): # Store the head of the # linked list into a # temporary node* and # iterate tmp = head while (tmp != None): print(tmp.data, end = " -> ") tmp = tmp.next # Function takes the head of the # LinkedList and the data as # argument and if no LinkedList # exists, it creates one with the # head pointing to first node. # If it exists already, it appends # given node at end of the last node def getData(head, num): # Create a new node temp = node(-1) tail = head # Insert data into the temporary # node and point it's next to NULL temp.data = num temp.next = None # Check if head is null, create a # linked list with temp as head # and tail of the list if (head == None): head = temp tail = temp # Else insert the temporary node # after the tail of the existing # node and make the temporary node # as the tail of the linked list else: while (tail != None): if (tail.next == None): tail.next = temp tail = tail.next tail = tail.next # Return the list return head # Function to concatenate the # two lists def mergelists(head1,head2): tail = head1 # Iterate through the head1 to # find the last node join the # next of last node of head1 # to the 1st node of head2 while (tail != None): if (tail.next == None and head2 != None): tail.next =head2 break tail = tail.next # return the concatenated # lists as a single list # - head1 return head1 # Sort the linked list using # bubble sort def sortlist(head1): curr = head1 temp = head1 # Compares two adjacent elements # and swaps if the first element # is greater than the other one. while (curr.next != None): temp = curr.next while (temp != None): if (temp.data < curr.data): t = temp.data temp.data = curr.data curr.data = t temp = temp.next curr = curr.next # Driver Code if __name__ == '__main__': head1 = node(-1) head2 = node(-1) head1 = None head2 = None # Given Linked List 1 head1 = getData(head1, 4) head1 = getData(head1, 7) head1 = getData(head1, 5) # Given Linked List 2 head2 = getData(head2, 2) head2 = getData(head2, 1) head2 = getData(head2, 8) head2 = getData(head2, 1) # Merge the two lists # in a single list head1 = mergelists(head1,head2) # Sort the unsorted merged list sortlist(head1) # Print the final # sorted merged list setData(head1) # This code is contributed by Mohit Kumar 29
C#
// C# program for
// the above approach
using System;
class GFG{
static node head1 = null;
static node head2 = null;
// Create structure for a node
class node
{
public int data;
public node next;
};
// Function to print
// the linked list
static void setData(node head)
{
node tmp;
// Store the head of the linked
// list into a temporary node
// and iterate
tmp = head;
while (tmp != null)
{
Console.Write(tmp.data + " -> ");
tmp = tmp.next;
}
}
// Function takes the head of
//the List and the data as
// argument and if no List
// exists, it creates one with the
// head pointing to first node.
// If it exists already, it appends
// given node at end of the last node
static node getData(node head, int num)
{
// Create a new node
node temp = new node();
node tail = head;
// Insert data into the temporary
// node and point it's next to null
temp.data = num;
temp.next = null;
// Check if head is null, create a
// linked list with temp as head
// and tail of the list
if (head == null)
{
head = temp;
tail = temp;
}
// Else insert the temporary node
// after the tail of the existing
// node and make the temporary node
// as the tail of the linked list
else
{
while (tail != null)
{
if (tail.next == null)
{
tail.next = temp;
tail = tail.next;
}
tail = tail.next;
}
}
// Return the list
return head;
}
// Function to concatenate
// the two lists
static node mergelists()
{
node tail = head1;
// Iterate through the
// head1 to find the
// last node join the
// next of last node
// of head1 to the
// 1st node of head2
while (tail != null)
{
if (tail.next == null &&
head2 != null)
{
tail.next = head2;
break;
}
tail = tail.next;
}
// return the concatenated
// lists as a single list - head1
return head1;
}
// Sort the linked list
// using bubble sort
static void sortlist()
{
node curr = head1;
node temp = head1;
// Compares two adjacent elements
// and swaps if the first element
// is greater than the other one.
while (curr.next != null)
{
temp = curr.next;
while (temp != null)
{
if (temp.data < curr.data)
{
int t = temp.data;
temp.data = curr.data;
curr.data = t;
}
temp = temp.next;
}
curr = curr.next;
}
}
// Driver Code
public static void Main(String[] args)
{
// Given Linked List 1
head1 = getData(head1, 4);
head1 = getData(head1, 7);
head1 = getData(head1, 5);
// Given Linked List 2
head2 = getData(head2, 2);
head2 = getData(head2, 1);
head2 = getData(head2, 8);
head2 = getData(head2, 1);
// Merge the two lists
// in a single list
head1 = mergelists();
// Sort the unsorted merged list
sortlist();
// Print the final
// sorted merged list
setData(head1);
}
}
// This code is contributed by Amit Katiyar
Javascript
<script>
// javascript program for
// the above approach
var head1 = null;
var head2 = null;
// Create structure for a node
class node {
constructor(){
this.data=0;
this.next = null;
}
}
// Function to print
// the linked list
function setData( head) {
var tmp;
// Store the head of the linked
// list into a temporary node
// and iterate
tmp = head;
while (tmp != null) {
document.write(tmp.data + " -> ");
tmp = tmp.next;
}
}
// Function takes the head of the
// LinkedList and the data as
// argument and if no LinkedList
// exists, it creates one with the
// head pointing to first node.
// If it exists already, it appends
// given node at end of the last node
function getData( head , num) {
// Create a new node
temp = new node();
var tail = head;
// Insert data into the temporary
// node and point it's next to null
temp.data = num;
temp.next = null;
// Check if head is null, create a
// linked list with temp as head
// and tail of the list
if (head == null) {
head = temp;
tail = temp;
}
// Else insert the temporary node
// after the tail of the existing
// node and make the temporary node
// as the tail of the linked list
else {
while (tail != null) {
if (tail.next == null) {
tail.next = temp;
tail = tail.next;
}
tail = tail.next;
}
}
// Return the list
return head;
}
// Function to concatenate
// the two lists
function mergelists() {
tail = head1;
// Iterate through the
// head1 to find the
// last node join the
// next of last node
// of head1 to the
// 1st node of head2
while (tail != null) {
if (tail.next == null && head2 != null) {
tail.next = head2;
break;
}
tail = tail.next;
}
// return the concatenated
// lists as a single list - head1
return head1;
}
// Sort the linked list
// using bubble sort
function sortlist() {
curr = head1;
temp = head1;
// Compares two adjacent elements
// and swaps if the first element
// is greater than the other one.
while (curr.next != null) {
temp = curr.next;
while (temp != null) {
if (temp.data < curr.data) {
var t = temp.data;
temp.data = curr.data;
curr.data = t;
}
temp = temp.next;
}
curr = curr.next;
}
}
// Driver Code
// Given Linked List 1
head1 = getData(head1, 4);
head1 = getData(head1, 7);
head1 = getData(head1, 5);
// Given Linked List 2
head2 = getData(head2, 2);
head2 = getData(head2, 1);
head2 = getData(head2, 8);
head2 = getData(head2, 1);
// Merge the two lists
// in a single list
head1 = mergelists();
// Sort the unsorted merged list
sortlist();
// Print the final
// sorted merged list
setData(head1);
// This code is contributed by umadevi9616.
</script>
Producción:
1 -> 1 -> 2 -> 4 -> 5 -> 7 -> 8
Complejidad de tiempo: O ((M + N) ^ 2) donde M y N son las longitudes de las dos listas vinculadas dadas. Estamos fusionando las dos listas y realizando una ordenación de burbujas en la lista fusionada. La complejidad temporal del tipo de burbuja es cuadrática.
Espacio Auxiliar : O(1)
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