Combinar una lista vinculada en otra lista vinculada en posiciones alternativas

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.

Complete Interview Preparation - GFG

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>
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.

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

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *