Dadas dos listas ordenadas, combínelas para producir una lista ordenada combinada (sin usar espacio adicional).
Ejemplos:
Input : head1: 5->7->9
head2: 4->6->8
Output : 4->5->6->7->8->9
Explanation: The output list is in sorted order.
Input : head1: 1->3->5->7
head2: 2->4
Output : 1->2->3->4->5->7
Explanation: The output list is in sorted order.
Hay diferentes soluciones discutidas en la publicación a continuación.
Combinar dos listas enlazadas ordenadas
Método 1 (recursivo):
Enfoque: la solución recursiva se puede formar, dado que las listas enlazadas están ordenadas.
- Compare el encabezado de ambas listas enlazadas.
- Encuentra el Node más pequeño entre los dos Nodes principales. El elemento actual será el Node más pequeño entre dos Nodes principales.
- El resto de elementos de ambas listas aparecerán después de eso.
- Ahora ejecute una función recursiva con parámetros, el siguiente Node del elemento más pequeño y la otra cabeza.
- La función recursiva devolverá el siguiente elemento más pequeño vinculado con el resto del elemento ordenado. Ahora apunte el siguiente elemento actual a eso, es decir, curr_ele->next=recursivefunction()
- Manejar algunos casos de esquina.
- Si ambas cabezas son NULL, devuelve nulo.
- Si una cabeza es nula, devuelve la otra.
Implementación:
C++
// C++ program to merge two sorted linked lists
// in-place.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
struct Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print linked list
void printList(Node* node)
{
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node* merge(Node* h1, Node* h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data) {
h1->next = merge(h1->next, h2);
return h1;
}
else {
h2->next = merge(h1, h2->next);
return h2;
}
}
// Driver program
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(3);
head1->next->next = newNode(5);
// 1->3->5 LinkedList created
Node* head2 = newNode(0);
head2->next = newNode(2);
head2->next->next = newNode(4);
// 0->2->4 LinkedList created
Node* mergedhead = merge(head1, head2);
printList(mergedhead);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to merge two sorted linked lists
// in-place.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
struct Node* temp = (Node*)malloc(sizeof(Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print linked list
void printList(Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node* merge(Node* h1, Node* h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data) {
h1->next = merge(h1->next, h2);
return h1;
}
else {
h2->next = merge(h1, h2->next);
return h2;
}
}
// Driver program
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(3);
head1->next->next = newNode(5);
// 1->3->5 LinkedList created
Node* head2 = newNode(0);
head2->next = newNode(2);
head2->next->next = newNode(4);
// 0->2->4 LinkedList created
Node* mergedhead = merge(head1, head2);
printList(mergedhead);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to merge two sorted
// linked lists in-place.
class GFG {
static class Node {
int data;
Node next;
};
// Function to create newNode in a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
static void printList(Node node)
{
while (node != null) {
System.out.printf("%d ", node.data);
node = node.next;
}
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
static Node merge(Node h1, Node h2)
{
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data) {
h1.next = merge(h1.next, h2);
return h1;
}
else {
h2.next = merge(h1, h2.next);
return h2;
}
}
// Driver program
public static void main(String args[])
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1.3.5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0.2.4 LinkedList created
Node mergedhead = merge(head1, head2);
printList(mergedhead);
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 program to merge two # sorted linked lists in-place. import math class Node: def __init__(self, data): self.data = data self.next = None # Function to create newNode in a linkedlist def newNode( key): temp = Node(key) temp.data = key temp.next = None return temp # A utility function to print linked list def printList( node): while (node != None): print(node.data, end = " ") node = node.next # Merges two given lists in-place. # This function mainly compares # head nodes and calls mergeUtil() def merge( h1, h2): if (h1 == None): return h2 if (h2 == None): return h1 # start with the linked list # whose head data is the least if (h1.data < h2.data): h1.next = merge(h1.next, h2) return h1 else: h2.next = merge(h1, h2.next) return h2 # Driver Code if __name__=='__main__': head1 = newNode(1) head1.next = newNode(3) head1.next.next = newNode(5) # 1.3.5 LinkedList created head2 = newNode(0) head2.next = newNode(2) head2.next.next = newNode(4) # 0.2.4 LinkedList created mergedhead = merge(head1, head2) printList(mergedhead) # This code is contributed by Srathore
C#
// C# program to merge two sorted
// linked lists in-place.
using System;
class GFG {
public class Node {
public int data;
public Node next;
};
// Function to create newNode in a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
static void printList(Node node)
{
while (node != null) {
Console.Write("{0} ", node.data);
node = node.next;
}
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
static Node merge(Node h1, Node h2)
{
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data) {
h1.next = merge(h1.next, h2);
return h1;
}
else {
h2.next = merge(h1, h2.next);
return h2;
}
}
// Driver code
public static void Main(String[] args)
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1.3.5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0.2.4 LinkedList created
Node mergedhead = merge(head1, head2);
printList(mergedhead);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// javascript program to merge two sorted
// linked lists in-place.
class Node {
constructor(){
this.data = 0;
this.next = null;
}
}
// Function to create newNode in a linkedlist
function newNode(key) {
temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
function printList( node) {
while (node != null) {
document.write(node.data+" ");
node = node.next;
}
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
function merge( h1, h2) {
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data) {
h1.next = merge(h1.next, h2);
return h1;
} else {
h2.next = merge(h1, h2.next);
return h2;
}
}
// Driver program
head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1.3.5 LinkedList created
head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0.2.4 LinkedList created
mergedhead = merge(head1, head2);
printList(mergedhead);
// This code contributed by umadevi9616
</script>
Producción
0 1 2 3 4 5
Análisis de Complejidad:
- Complejidad de tiempo: O (n), solo se necesita un recorrido de las listas vinculadas.
- Espacio auxiliar: O(n), si se tiene en cuenta el espacio de pila recursivo.
Método 2 (iterativo):
Enfoque: Este enfoque es muy similar al enfoque recursivo anterior.
- Recorra la lista de principio a fin.
- Si el Node principal de la segunda lista se encuentra entre dos Nodes de la primera lista, insértelo allí y haga que el siguiente Node de la segunda lista sea el encabezado. Continúe hasta que no quede ningún Node en ambas listas, es decir, se recorren ambas listas.
- Si la primera lista ha llegado al final durante el recorrido, apunte el siguiente Node al encabezado de la segunda lista.
Nota: Compare ambas listas donde la lista con un valor de cabeza más pequeño es la primera lista.
Implementación:
C++
// C++ program to merge two sorted linked lists
// in-place.
#include <bits/stdc++.h>
using namespace std;
struct Node {
int data;
struct Node* next;
};
// Function to create newNode in a linkedlist
struct Node* newNode(int key)
{
struct Node* temp = new Node;
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print linked list
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
struct Node* mergeUtil(struct Node* h1, struct Node* h2)
{
// if only one node in first list
// simply point its head to second list
if (!h1->next) {
h1->next = h2;
return h1;
}
// Initialize current and next pointers of
// both lists
struct Node *curr1 = h1, *next1 = h1->next;
struct Node *curr2 = h2, *next2 = h2->next;
while (next1 && curr2) {
// if curr2 lies in between curr1 and next1
// then do curr1->curr2->next1
if ((curr2->data) >= (curr1->data)
&& (curr2->data) <= (next1->data)) {
next2 = curr2->next;
curr1->next = curr2;
curr2->next = next1;
// now let curr1 and curr2 to point
// to their immediate next pointers
curr1 = curr2;
curr2 = next2;
}
else {
// if more nodes in first list
if (next1->next) {
next1 = next1->next;
curr1 = curr1->next;
}
// else point the last node of first list
// to the remaining nodes of second list
else {
next1->next = curr2;
return h1;
}
}
}
return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
struct Node* merge(struct Node* h1, struct Node* h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
return mergeUtil(h1, h2);
else
return mergeUtil(h2, h1);
}
// Driver program
int main()
{
struct Node* head1 = newNode(1);
head1->next = newNode(3);
head1->next->next = newNode(5);
// 1->3->5 LinkedList created
struct Node* head2 = newNode(0);
head2->next = newNode(2);
head2->next->next = newNode(4);
// 0->2->4 LinkedList created
struct Node* mergedhead = merge(head1, head2);
printList(mergedhead);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to merge two sorted linked lists
// in-place.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to create newNode in a linkedlist
Node* newNode(int key)
{
Node* temp = (Node *)malloc(sizeof(Node));
temp->data = key;
temp->next = NULL;
return temp;
}
// A utility function to print linked list
void printList(Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
struct Node* mergeUtil(Node* h1, Node* h2)
{
// if only one node in first list
// simply point its head to second list
if (!h1->next) {
h1->next = h2;
return h1;
}
// Initialize current and next pointers of both lists
Node *curr1 = h1, *next1 = h1->next;
Node *curr2 = h2, *next2 = h2->next;
while (next1 && curr2) {
// if curr2 lies in between curr1 and next1
// then do curr1->curr2->next1
if ((curr2->data) >= (curr1->data)
&& (curr2->data) <= (next1->data)) {
next2 = curr2->next;
curr1->next = curr2;
curr2->next = next1;
// now let curr1 and curr2 to point
// to their immediate next pointers
curr1 = curr2;
curr2 = next2;
}
else {
// if more nodes in first list
if (next1->next) {
next1 = next1->next;
curr1 = curr1->next;
}
// else point the last node of first list
// to the remaining nodes of second list
else {
next1->next = curr2;
return h1;
}
}
}
return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
Node* merge(Node* h1, Node* h2)
{
if (!h1)
return h2;
if (!h2)
return h1;
// start with the linked list
// whose head data is the least
if (h1->data < h2->data)
return mergeUtil(h1, h2);
else
return mergeUtil(h2, h1);
}
// Driver program
int main()
{
Node* head1 = newNode(1);
head1->next = newNode(3);
head1->next->next = newNode(5);
// 1->3->5 LinkedList created
Node* head2 = newNode(0);
head2->next = newNode(2);
head2->next->next = newNode(4);
// 0->2->4 LinkedList created
Node* mergedhead = merge(head1, head2);
printList(mergedhead);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to merge two sorted
// linked lists in-place.
class GfG {
static class Node {
int data;
Node next;
}
// Function to create newNode in a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
static void printList(Node node)
{
while (node != null) {
System.out.print(node.data + " ");
node = node.next;
}
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
static Node mergeUtil(Node h1, Node h2)
{
// if only one node in first list
// simply point its head to second list
if (h1.next == null) {
h1.next = h2;
return h1;
}
// Initialize current and next pointers of
// both lists
Node curr1 = h1, next1 = h1.next;
Node curr2 = h2, next2 = h2.next;
while (next1 != null && curr2 != null) {
// if curr2 lies in between curr1 and next1
// then do curr1->curr2->next1
if ((curr2.data) >= (curr1.data) && (curr2.data) <= (next1.data)) {
next2 = curr2.next;
curr1.next = curr2;
curr2.next = next1;
// now let curr1 and curr2 to point
// to their immediate next pointers
curr1 = curr2;
curr2 = next2;
}
else {
// if more nodes in first list
if (next1.next != null) {
next1 = next1.next;
curr1 = curr1.next;
}
// else point the last node of first list
// to the remaining nodes of second list
else {
next1.next = curr2;
return h1;
}
}
}
return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
static Node merge(Node h1, Node h2)
{
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data)
return mergeUtil(h1, h2);
else
return mergeUtil(h2, h1);
}
// Driver code
public static void main(String[] args)
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1->3->5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0->2->4 LinkedList created
Node mergedhead = merge(head1, head2);
printList(mergedhead);
}
}
// This code is contributed by
// prerna saini
Python
# Python program to merge two sorted linked lists # in-place. # Linked List node class Node: def __init__(self, data): self.data = data self.next = None # Function to create newNode in a linkedlist def newNode(key): temp = Node(0) temp.data = key temp.next = None return temp # A utility function to print linked list def printList(node): while (node != None) : print( node.data, end =" ") node = node.next # Merges two lists with headers as h1 and h2. # It assumes that h1's data is smaller than # or equal to h2's data. def mergeUtil(h1, h2): # if only one node in first list # simply point its head to second list if (h1.next == None) : h1.next = h2 return h1 # Initialize current and next pointers of # both lists curr1 = h1 next1 = h1.next curr2 = h2 next2 = h2.next while (next1 != None and curr2 != None): # if curr2 lies in between curr1 and next1 # then do curr1.curr2.next1 if ((curr2.data) >= (curr1.data) and (curr2.data) <= (next1.data)) : next2 = curr2.next curr1.next = curr2 curr2.next = next1 # now let curr1 and curr2 to point # to their immediate next pointers curr1 = curr2 curr2 = next2 else : # if more nodes in first list if (next1.next) : next1 = next1.next curr1 = curr1.next # else point the last node of first list # to the remaining nodes of second list else : next1.next = curr2 return h1 return h1 # Merges two given lists in-place. This function # mainly compares head nodes and calls mergeUtil() def merge( h1, h2): if (h1 == None): return h2 if (h2 == None): return h1 # start with the linked list # whose head data is the least if (h1.data < h2.data): return mergeUtil(h1, h2) else: return mergeUtil(h2, h1) # Driver program head1 = newNode(1) head1.next = newNode(3) head1.next.next = newNode(5) # 1.3.5 LinkedList created head2 = newNode(0) head2.next = newNode(2) head2.next.next = newNode(4) # 0.2.4 LinkedList created mergedhead = merge(head1, head2) printList(mergedhead) # This code is contributed by Arnab Kundu
C#
// C# program to merge two sorted
// linked lists in-place.
using System;
class GfG {
public class Node {
public int data;
public Node next;
}
// Function to create newNode in a linkedlist
static Node newNode(int key)
{
Node temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
static void printList(Node node)
{
while (node != null) {
Console.Write(node.data + " ");
node = node.next;
}
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
static Node mergeUtil(Node h1, Node h2)
{
// if only one node in first list
// simply point its head to second list
if (h1.next == null) {
h1.next = h2;
return h1;
}
// Initialize current and next pointers of
// both lists
Node curr1 = h1, next1 = h1.next;
Node curr2 = h2, next2 = h2.next;
while (next1 != null && curr2 != null) {
// if curr2 lies in between curr1 and next1
// then do curr1->curr2->next1
if ((curr2.data) >= (curr1.data)
&& (curr2.data) <= (next1.data)) {
next2 = curr2.next;
curr1.next = curr2;
curr2.next = next1;
// now let curr1 and curr2 to point
// to their immediate next pointers
curr1 = curr2;
curr2 = next2;
}
else {
// if more nodes in first list
if (next1.next != null) {
next1 = next1.next;
curr1 = curr1.next;
}
// else point the last node of first list
// to the remaining nodes of second list
else {
next1.next = curr2;
return h1;
}
}
}
return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
static Node merge(Node h1, Node h2)
{
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data)
return mergeUtil(h1, h2);
else
return mergeUtil(h2, h1);
}
// Driver code
public static void Main(String[] args)
{
Node head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1->3->5 LinkedList created
Node head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0->2->4 LinkedList created
Node mergedhead = merge(head1, head2);
printList(mergedhead);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript program to merge two sorted
// linked lists in-place.
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to create newNode in a linkedlist
function newNode(key) {
var temp = new Node();
temp.data = key;
temp.next = null;
return temp;
}
// A utility function to print linked list
function printList(node) {
while (node != null) {
document.write(node.data + " ");
node = node.next;
}
}
// Merges two lists with headers as h1 and h2.
// It assumes that h1's data is smaller than
// or equal to h2's data.
function mergeUtil(h1, h2) {
// if only one node in first list
// simply point its head to second list
if (h1.next == null) {
h1.next = h2;
return h1;
}
// Initialize current and next pointers of
// both lists
var curr1 = h1, next1 = h1.next;
var curr2 = h2, next2 = h2.next;
while (next1 != null && curr2 != null) {
// if curr2 lies in between curr1 and next1
// then do curr1->curr2->next1
if ((curr2.data) >= (curr1.data) &&
(curr2.data) <= (next1.data)) {
next2 = curr2.next;
curr1.next = curr2;
curr2.next = next1;
// now let curr1 and curr2 to point
// to their immediate next pointers
curr1 = curr2;
curr2 = next2;
} else {
// if more nodes in first list
if (next1.next != null) {
next1 = next1.next;
curr1 = curr1.next;
}
// else point the last node of first list
// to the remaining nodes of second list
else {
next1.next = curr2;
return h1;
}
}
}
return h1;
}
// Merges two given lists in-place. This function
// mainly compares head nodes and calls mergeUtil()
function merge(h1, h2) {
if (h1 == null)
return h2;
if (h2 == null)
return h1;
// start with the linked list
// whose head data is the least
if (h1.data < h2.data)
return mergeUtil(h1, h2);
else
return mergeUtil(h2, h1);
}
// Driver code
var head1 = newNode(1);
head1.next = newNode(3);
head1.next.next = newNode(5);
// 1->3->5 LinkedList created
var head2 = newNode(0);
head2.next = newNode(2);
head2.next.next = newNode(4);
// 0->2->4 LinkedList created
var mergedhead = merge(head1, head2);
printList(mergedhead);
// This code contributed by gauravrajput1
</script>
Producción
0 1 2 3 4 5
Análisis de Complejidad:
- Complejidad de tiempo: O (n), ya que solo se necesita un recorrido de las listas vinculadas.
- Espacio Auxiliar: O(1), Ya que no se requiere espacio.
Este artículo es una contribución de Mandula Vikitha . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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