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 la 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 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.
Java
// Java program to merge a linked list
// into another at alternate positions
class LinkedList
{
// head of list
Node head;
// Linked list Node
class Node
{
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
/* Inserts a new Node at front
of the list. */
void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
// 3. Make next of new Node as head
new_node.next = head;
/* 4. Move the head to point to new
Node */
head = new_node;
}
// 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(LinkedList q)
{
Node p_curr = head,
q_curr = q.head;
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;
}
q.head = q_curr;
}
// Function to print linked list
void printList()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String args[])
{
LinkedList llist1 =
new LinkedList();
LinkedList llist2 =
new LinkedList();
llist1.push(3);
llist1.push(2);
llist1.push(1);
System.out.println(
"First Linked List:");
llist1.printList();
llist2.push(8);
llist2.push(7);
llist2.push(6);
llist2.push(5);
llist2.push(4);
System.out.println(
"Second Linked List:");
llist1.merge(llist2);
System.out.println(
"Modified first linked list:");
llist1.printList();
System.out.println(
"Modified second linked list:");
llist2.printList();
}
}
// This code is contributed by Rajat Mishra
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(N)
Espacio Auxiliar: O(1)
Consulte el artículo completo sobre Fusionar 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