Dadas dos listas vinculadas, inserte Nodes de la segunda lista en la primera lista en posiciones alternativas de la primera lista.
Por ejemplo, si la primera lista es 5->7->17->13->11 y la segunda es 12->10->2->4->6, la primera lista debería convertirse en 5->12->7- >10->17->2->13->4->11->6 y la segunda lista debería quedar vacía. Los Nodes de la segunda lista solo deben insertarse cuando haya posiciones disponibles. Por ejemplo, si la primera lista es 1->2->3 y la segunda lista es 4->5->6->7->8, entonces la primera lista debería convertirse en 1->4->2->5-> 3->6 y segunda lista a 7->8.
No se permite el uso de espacio adicional (no se permite crear Nodes adicionales), es decir, la inserción debe realizarse en el lugar. La complejidad de tiempo esperada es O(n) donde n es el número de Nodes en la primera lista.
La idea es ejecutar un bucle mientras haya posiciones disponibles en el primer bucle e insertar Nodes de la segunda lista cambiando los punteros. Las siguientes son implementaciones de este enfoque.
C++
// C++ program to merge a linked list
// into another at alternate positions
#include <bits/stdc++.h>
using namespace std;
// A nexted list node
class Node
{
public:
int data;
Node *next;
};
/* Function to insert a node
at the beginning */
void push(Node ** head_ref,
int new_data)
{
Node* new_node = new Node();
new_node->data = new_data;
new_node->next = (*head_ref);
(*head_ref) = new_node;
}
/* Utility function to print a
singly linked list */
void printList(Node *head)
{
Node *temp = head;
while (temp != NULL)
{
cout << temp -> data << " ";
temp = temp -> next;
}
cout << endl;
}
// Main function that inserts nodes of
// linked list q into p at alternate positions.
// Since head of first list never changes and
// head of second list may change, we need single
// pointer for first list and double pointer for
// second list.
void merge(Node *p, Node **q)
{
Node *p_curr = p, *q_curr = *q;
Node *p_next, *q_next;
// While there are available positions
// in p
while (p_curr != NULL &&
q_curr != NULL)
{
// Save next pointers
p_next = p_curr->next;
q_next = q_curr->next;
// Make q_curr as next of p_curr
// Change next pointer of q_curr
q_curr->next = p_next;
// Change next pointer of p_curr
p_curr->next = q_curr;
// Update current pointers for
// next iteration
p_curr = p_next;
q_curr = q_next;
}
// Update head pointer of second list
*q = q_curr;
}
// Driver code
int main()
{
Node *p = NULL, *q = NULL;
push(&p, 3);
push(&p, 2);
push(&p, 1);
cout << "First Linked List:";
printList(p);
push(&q, 8);
push(&q, 7);
push(&q, 6);
push(&q, 5);
push(&q, 4);
cout << "Second Linked List:";
printList(q);
merge(p, &q);
cout <<
"Modified First Linked List:";
printList(p);
cout <<
"Modified Second Linked List:";
printList(q);
return 0;
}
// This code is contributed by rathbhupendra
Producción:
First Linked List: 1 2 3 Second Linked List: 4 5 6 7 8 Modified First Linked List: 1 4 2 5 3 6 Modified Second Linked List: 7 8
Complejidad de tiempo: O(min(n1, n2)), donde n1 y n2 representan la longitud de las dos listas enlazadas dadas.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.
Consulte el artículo completo sobre Fusionar una lista vinculada en otra lista vinculada en posiciones alternativas para obtener más detalles.
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