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 q_curr->next = p_next; // Change next pointer of q_curr p_curr->next = q_curr; // Change next pointer of p_curr // Update current pointers for next iteration p_curr = p_next; q_curr = q_next; } *q = q_curr; // Update head pointer of second list } // Driver code int main() { Node *p = NULL, *q = NULL; push(&p, 3); push(&p, 2); push(&p, 1); cout<<"First Linked List:\n"; printList(p); push(&q, 8); push(&q, 7); push(&q, 6); push(&q, 5); push(&q, 4); cout<<"Second Linked List:\n"; printList(q); merge(p, &q); cout<<"Modified First Linked List:\n"; printList(p); cout<<"Modified Second Linked List:\n"; printList(q); return 0; } // This code is contributed by rathbhupendra
C
// C program to merge a linked list into another at // alternate positions #include <stdio.h> #include <stdlib.h> // A nexted list node struct Node { int data; struct Node *next; }; /* Function to insert a node at the beginning */ void push(struct Node ** head_ref, int new_data) { struct Node* new_node = (struct Node*) malloc(sizeof(struct 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(struct Node *head) { struct Node *temp = head; while (temp != NULL) { printf("%d ", temp->data); temp = temp->next; } printf("\n"); } // 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(struct Node *p, struct Node **q) { struct Node *p_curr = p, *q_curr = *q; struct 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 q_curr->next = p_next; // Change next pointer of q_curr p_curr->next = q_curr; // Change next pointer of p_curr // Update current pointers for next iteration p_curr = p_next; q_curr = q_next; } *q = q_curr; // Update head pointer of second list } // Driver program to test above functions int main() { struct Node *p = NULL, *q = NULL; push(&p, 3); push(&p, 2); push(&p, 1); printf("First Linked List:\n"); printList(p); push(&q, 8); push(&q, 7); push(&q, 6); push(&q, 5); push(&q, 4); printf("Second Linked List:\n"); printList(q); merge(p, &q); printf("Modified First Linked List:\n"); printList(p); printf("Modified Second Linked List:\n"); printList(q); getchar(); return 0; }
Java
// Java program to merge a linked list into another at // alternate positions class LinkedList { Node head; // head of list /* 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 q_curr.next = p_next; // change next pointer of q_curr p_curr.next = q_curr; // change next pointer of p_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 program to test above functions */ 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 */
Python3
# Python program to merge a linked list into another at # alternate positions class Node(object): def __init__(self, data:int): self.data = data self.next = None class LinkedList(object): def __init__(self): self.head = None def push(self, new_data:int): new_node = Node(new_data) new_node.next = self.head # 4. Move the head to point to new Node self.head = new_node # Function to print linked list from the Head def printList(self): temp = self.head while temp != None: print(temp.data) temp = temp.next # Main function that inserts nodes of linked list q into p at alternate positions. # Since head of first list never changes # but head of second list/ may change, # we need single pointer for first list and double pointer for second list. def merge(self, p, q): p_curr = p.head q_curr = q.head # swap their positions until one finishes off while p_curr != None and q_curr != None: # Save next pointers p_next = p_curr.next q_next = q_curr.next # make q_curr as next of p_curr q_curr.next = p_next # change next pointer of q_curr p_curr.next = q_curr # change next pointer of p_curr # update current pointers for next iteration p_curr = p_next q_curr = q_next q.head = q_curr # Driver program to test above functions llist1 = LinkedList() llist2 = LinkedList() # Creating LLs # 1. llist1.push(3) llist1.push(2) llist1.push(1) llist1.push(0) # 2. for i in range(8, 3, -1): llist2.push(i) print("First Linked List:") llist1.printList() print("Second Linked List:") llist2.printList() # Merging the LLs llist1.merge(p=llist1, q=llist2) print("Modified first linked list:") llist1.printList() print("Modified second linked list:") llist2.printList() # This code is contributed by Deepanshu Mehta
C#
// C# program to merge a linked list into // another at alternate positions using System; public class LinkedList { Node head; // head of list /* Linked list Node*/ public class Node { public int data; public Node next; public 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 q_curr.next = p_next; // change next pointer of q_curr p_curr.next = q_curr; // change next pointer of p_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) { Console.Write(temp.data+" "); temp = temp.next; } Console.WriteLine(); } /* Driver code*/ public static void Main() { LinkedList llist1 = new LinkedList(); LinkedList llist2 = new LinkedList(); llist1.push(3); llist1.push(2); llist1.push(1); Console.WriteLine("First Linked List:"); llist1.printList(); llist2.push(8); llist2.push(7); llist2.push(6); llist2.push(5); llist2.push(4); Console.WriteLine("Second Linked List:"); llist1.merge(llist2); Console.WriteLine("Modified first linked list:"); llist1.printList(); Console.WriteLine("Modified second linked list:"); llist2.printList(); } } /* This code contributed by PrinciRaj1992 */
Javascript
<script> // Javascript program to merge a linked list into another at // alternate positions // A nexted list node class Node { constructor() { this.data = 0; this.next = null; } }; /* Function to insert a node at the beginning */ function push(head_ref, new_data) { var new_node = new Node(); new_node.data = new_data; new_node.next = (head_ref); (head_ref) = new_node; return head_ref; } /* Utility function to print a singly linked list */ function printList(head) { var temp = head; while (temp != null) { document.write( temp.data + " "); temp = temp.next; } document.write("<br>"); } // 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. function merge(p, q) { var p_curr = p, q_curr = q; var 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 q_curr.next = p_next; // Change next pointer of q_curr p_curr.next = q_curr; // Change next pointer of p_curr // Update current pointers for next iteration p_curr = p_next; q_curr = q_next; } q = q_curr; // Update head pointer of second list return q; } // Driver code var p = null, q = null; p = push(p, 3); p = push(p, 2); p = push(p, 1); document.write( "First Linked List:<br>"); printList(p); q = push(q, 8); q = push(q, 7); q = push(q, 6); q = push(q, 5); q = push(q, 4); document.write( "Second Linked List:<br>"); printList(q); q = merge(p, q); document.write( "Modified First Linked List:<br>"); printList(p); document.write( "Modified Second Linked List:<br>"); printList(q); // This code is contributed by rrrtnx. </script>
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.
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