Dada una lista enlazada que contiene n Nodes. El problema es insertar un nuevo Node con datos x en el medio de la lista. Si n es par, entonces inserte el nuevo Node después del (n/2) enésimo Node, de lo contrario, inserte el nuevo Node después del (n+1)/2 enésimo Node.
Ejemplos:
Input : list: 1->2->4->5
x = 3
Output : 1->2->3->4->5
Input : list: 5->10->4->32->16
x = 41
Output : 5->10->4->41->32->16
Método 1 (Usando la longitud de la lista enlazada):
Encuentre la cantidad de Nodes o la longitud del enlace usando un recorrido. Que sea len . Calcule c = (len/2), si len es par, de lo contrario, c = (len+1)/2, si len es impar. Atraviese de nuevo los primeros c Nodes e inserte el nuevo Node después del c -ésimo Node.
Java
// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList
{
static Node head; // head of list
/* Node Class */
static class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d) {
data = d;
next = null;
}
}
// function to insert node at the
// middle of the linked list
static void insertAtMid(int x)
{
// if list is empty
if (head == null)
head = new Node(x);
else {
// get a new node
Node newNode = new Node(x);
Node ptr = head;
int len = 0;
// calculate length of the linked list
//, i.e, the number of nodes
while (ptr != null) {
len++;
ptr = ptr.next;
}
// 'count' the number of nodes after which
// the new node is to be inserted
int count = ((len % 2) == 0) ? (len / 2) :
(len + 1) / 2;
ptr = head;
// 'ptr' points to the node after which
// the new node is to be inserted
while (count-- > 1)
ptr = ptr.next;
// insert the 'newNode' and adjust
// the required links
newNode.next = ptr.next;
ptr.next = newNode;
}
}
// function to display the linked list
static void display()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
// Driver program to test above
public static void main (String[] args)
{
// Creating the list 1.2.4.5
head = null;
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(4);
head.next.next.next = new Node(5);
System.out.println("Linked list before "+
"insertion: ");
display();
int x = 3;
insertAtMid(x);
System.out.println("
Linked list after"+
" insertion: ");
display();
}
}
// This article is contributed by Chhavi
Producción:
Linked list before insertion: 1 2 4 5 Linked list after insertion: 1 2 3 4 5
Complejidad de tiempo: O(n)
Complejidad espacial : O(1) usando espacio constante
Método 2 (usando dos punteros):
basado en el algoritmo de Turtle y liebre que usa dos punteros, uno conocido como lento y el otro conocido como rápido . Este algoritmo ayuda a encontrar el Node medio de la lista enlazada. Se explica en el procedimiento de división frontal y negro de esta publicación. Ahora, puede insertar el nuevo Node después del Node medio obtenido del proceso anterior. Este enfoque requiere solo un único recorrido de la lista.
Java
// Java implementation to insert node
// at the middle of the linked list
import java.util.*;
import java.lang.*;
import java.io.*;
class LinkedList
{
static Node head; // head of list
/* Node Class */
static class Node {
int data;
Node next;
// Constructor to create a new node
Node(int d) {
data = d;
next = null;
}
}
// function to insert node at the
// middle of the linked list
static void insertAtMid(int x)
{
// if list is empty
if (head == null)
head = new Node(x);
else {
// get a new node
Node newNode = new Node(x);
// assign values to the slow
// and fast pointers
Node slow = head;
Node fast = head.next;
while (fast != null && fast.next
!= null)
{
// move slow pointer to next node
slow = slow.next;
// move fast pointer two nodes
// at a time
fast = fast.next.next;
}
// insert the 'newNode' and adjust
// the required links
newNode.next = slow.next;
slow.next = newNode;
}
}
// function to display the linked list
static void display()
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
}
// Driver program to test above
public static void main (String[] args)
{
// Creating the list 1.2.4.5
head = null;
head = new Node(1);
head.next = new Node(2);
head.next.next = new Node(4);
head.next.next.next = new Node(5);
System.out.println("Linked list before"+
" insertion: ");
display();
int x = 3;
insertAtMid(x);
System.out.println("
Linked list after"+
" insertion: ");
display();
}
}
// This article is contributed by Chhavi
Producción:
Linked list before insertion: 1 2 4 5 Linked list after insertion: 1 2 3 4 5
Complejidad de tiempo: O(n)
Complejidad del espacio : O(n) donde n es el tamaño de la lista enlazada
Consulte el artículo completo sobre Insertar Node en el medio de la lista vinculada 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