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