Dada una array de N elementos. La tarea es insertar los elementos dados en la posición media en la lista enlazada uno tras otro. Cada operación de inserción debe tener una complejidad de tiempo O(1).
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4, 5}
Salida: 1 -> 3 -> 5 -> 4 -> 2 -> NULL
1 -> NULL
1 -> 2 -> NULL
1 -> 3 -> 2 -> NULO
1 -> 3 -> 4 -> 2 -> NULO
1 -> 3 -> 5 -> 4 -> 2 -> NULO
Entrada: arr[] = {5, 4, 1, 2}
Salida: 5 -> 1 -> 2 -> 4 -> NULO
Planteamiento: Hay dos casos:
- El número de elementos presentes en la lista es inferior a 2.
- El número de elementos presentes en la lista es más de 2.
- El número de elementos ya presentes es incluso decir N , luego el nuevo elemento se inserta en la posición media que es (N / 2) + 1 .
- El número de elementos ya presentes es impar, entonces el nuevo elemento se inserta al lado del elemento medio actual que es (N / 2) + 2 .
Tomamos un puntero adicional ‘medio’ que almacena la dirección del elemento medio actual y un contador que cuenta el número total de elementos.
Si los elementos ya presentes en la lista enlazada son menos de 2, el centro siempre apuntará a la primera posición e insertaremos el nuevo Node después del centro actual.
Si los elementos ya presentes en la lista enlazada son más de 2, insertamos el nuevo Node al lado del medio actual e incrementamos el contador.
Si hay un número impar de elementos después de la inserción, el puntero central apunta al Node recién insertado; de lo contrario, no hay cambios en el puntero central.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <iostream>
using namespace std;
// Node structure
struct Node {
int value;
struct Node* next;
};
// Class to represent a node
// of the linked list
class LinkedList {
private:
struct Node *head, *mid;
int count;
public:
LinkedList();
void insertAtMiddle(int);
void show();
};
LinkedList::LinkedList()
{
head = NULL;
mid = NULL;
count = 0;
}
// Function to insert a node in
// the middle of the linked list
void LinkedList::insertAtMiddle(int n)
{
struct Node* temp = new struct Node();
struct Node* temp1;
temp->next = NULL;
temp->value = n;
// If the number of elements
// already present are less than 2
if (count < 2) {
if (head == NULL) {
head = temp;
}
else {
temp1 = head;
temp1->next = temp;
}
count++;
// mid points to first element
mid = head;
}
// If the number of elements already present
// are greater than 2
else {
temp->next = mid->next;
mid->next = temp;
count++;
// If number of elements after insertion
// are odd
if (count % 2 != 0) {
// mid points to the newly
// inserted node
mid = mid->next;
}
}
}
// Function to print the nodes
// of the linked list
void LinkedList::show()
{
struct Node* temp;
temp = head;
// Initializing temp to head
// Iterating and printing till
// The end of linked list
// That is, till temp is null
while (temp != NULL) {
cout << temp->value << " -> ";
temp = temp->next;
}
cout << "NULL";
cout << endl;
}
// Driver code
int main()
{
// Elements to be inserted one after another
int arr[] = { 1, 2, 3, 4, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
LinkedList L1;
// Insert the elements
for (int i = 0; i < n; i++)
L1.insertAtMiddle(arr[i]);
// Print the nodes of the linked list
L1.show();
return 0;
}
Java
// Java implementation of the approach
class GFG
{
// Node ure
static class Node
{
int value;
Node next;
};
// Class to represent a node
// of the linked list
static class LinkedList
{
Node head, mid;
int count;
LinkedList()
{
head = null;
mid = null;
count = 0;
}
// Function to insert a node in
// the middle of the linked list
void insertAtMiddle(int n)
{
Node temp = new Node();
Node temp1;
temp.next = null;
temp.value = n;
// If the number of elements
// already present are less than 2
if (count < 2)
{
if (head == null)
{
head = temp;
}
else
{
temp1 = head;
temp1.next = temp;
}
count++;
// mid points to first element
mid = head;
}
// If the number of elements already present
// are greater than 2
else
{
temp.next = mid.next;
mid.next = temp;
count++;
// If number of elements after insertion
// are odd
if (count % 2 != 0)
{
// mid points to the newly
// inserted node
mid = mid.next;
}
}
}
// Function to print the nodes
// of the linked list
void show()
{
Node temp;
temp = head;
// Initializing temp to head
// Iterating and printing till
// The end of linked list
// That is, till temp is null
while (temp != null)
{
System.out.print( temp.value + " -> ");
temp = temp.next;
}
System.out.print( "null");
System.out.println();
}
}
// Driver code
public static void main(String args[])
{
// Elements to be inserted one after another
int arr[] = { 1, 2, 3, 4, 5 };
int n = arr.length;
LinkedList L1=new LinkedList();
// Insert the elements
for (int i = 0; i < n; i++)
L1.insertAtMiddle(arr[i]);
// Print the nodes of the linked list
L1.show();
}
}
// This code is contributed by Arnab Kundu
Python3
# Python3 implementation of the approach # Node ure class Node: def __init__(self): self.value = 0 self.next = None # Class to represent a node # of the linked list class LinkedList: def __init__(self) : self.head = None self.mid = None self.count = 0 # Function to insert a node in # the middle of the linked list def insertAtMiddle(self , n): temp = Node() temp1 = None temp.next = None temp.value = n # If the number of elements # already present are less than 2 if (self.count < 2): if (self.head == None) : self.head = temp else: temp1 = self.head temp1.next = temp self.count = self.count + 1 # mid points to first element self.mid = self.head # If the number of elements already present # are greater than 2 else: temp.next = self.mid.next self.mid.next = temp self.count = self.count + 1 # If number of elements after insertion # are odd if (self.count % 2 != 0): # mid points to the newly # inserted node self.mid = self.mid.next # Function to print the nodes # of the linked list def show(self): temp = None temp = self.head # Initializing temp to self.head # Iterating and printing till # The end of linked list # That is, till temp is None while (temp != None) : print( temp.value, end = " -> ") temp = temp.next print( "None") # Driver code # Elements to be inserted one after another arr = [ 1, 2, 3, 4, 5] n = len(arr) L1 = LinkedList() # Insert the elements for i in range(n): L1.insertAtMiddle(arr[i]) # Print the nodes of the linked list L1.show() # This code is contributed by Arnab Kundu
C#
// C# implementation of the approach
using System;
class GFG
{
// Node ure
public class Node
{
public int value;
public Node next;
};
// Class to represent a node
// of the linked list
public class LinkedList
{
public Node head, mid;
public int count;
public LinkedList()
{
head = null;
mid = null;
count = 0;
}
// Function to insert a node in
// the middle of the linked list
public void insertAtMiddle(int n)
{
Node temp = new Node();
Node temp1;
temp.next = null;
temp.value = n;
// If the number of elements
// already present are less than 2
if (count < 2)
{
if (head == null)
{
head = temp;
}
else
{
temp1 = head;
temp1.next = temp;
}
count++;
// mid points to first element
mid = head;
}
// If the number of elements already present
// are greater than 2
else
{
temp.next = mid.next;
mid.next = temp;
count++;
// If number of elements after insertion
// are odd
if (count % 2 != 0)
{
// mid points to the newly
// inserted node
mid = mid.next;
}
}
}
// Function to print the nodes
// of the linked list
public void show()
{
Node temp;
temp = head;
// Initializing temp to head
// Iterating and printing till
// The end of linked list
// That is, till temp is null
while (temp != null)
{
Console.Write( temp.value + " -> ");
temp = temp.next;
}
Console.Write( "null");
Console.WriteLine();
}
}
// Driver code
public static void Main(String []args)
{
// Elements to be inserted one after another
int []arr = { 1, 2, 3, 4, 5 };
int n = arr.Length;
LinkedList L1=new LinkedList();
// Insert the elements
for (int i = 0; i < n; i++)
L1.insertAtMiddle(arr[i]);
// Print the nodes of the linked list
L1.show();
}
}
// This code contributed by Rajput-Ji
Javascript
<script>
// JavaScript implementation of the approach
// Node ure
class Node {
constructor() {
this.value = 0;
this.next = null;
}
}
// Class to represent a node
// of the linked list
class LinkedList {
constructor() {
this.head = null;
this.mid = null;
this.count = 0;
}
// Function to insert a node in
// the middle of the linked list
insertAtMiddle(n) {
var temp = new Node();
var temp1;
temp.next = null;
temp.value = n;
// If the number of elements
// already present are less than 2
if (this.count < 2) {
if (this.head == null) {
this.head = temp;
} else {
temp1 = this.head;
temp1.next = temp;
}
this.count++;
// mid points to first element
this.mid = this.head;
}
// If the number of elements already present
// are greater than 2
else {
temp.next = this.mid.next;
this.mid.next = temp;
this.count++;
// If number of elements after insertion
// are odd
if (this.count % 2 != 0) {
// mid points to the newly
// inserted node
this.mid = this.mid.next;
}
}
}
// Function to print the nodes
// of the linked list
show() {
var temp;
temp = this.head;
// Initializing temp to head
// Iterating and printing till
// The end of linked list
// That is, till temp is null
while (temp != null) {
document.write(temp.value + " -> ");
temp = temp.next;
}
document.write("null");
document.write("<br>");
}
}
// Driver code
// Elements to be inserted one after another
var arr = [1, 2, 3, 4, 5];
var n = arr.length;
var L1 = new LinkedList();
// Insert the elements
for (var i = 0; i < n; i++) L1.insertAtMiddle(arr[i]);
// Print the nodes of the linked list
L1.show();
</script>
Producción:
1 -> 3 -> 5 -> 4 -> 2 -> NULL
Complejidad de Tiempo: O(N)
Espacio Auxiliar: O(1), ya que no se ha tomado ningún espacio extra.
Publicación traducida automáticamente
Artículo escrito por RuchaDeodhar y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA