Inserte un Node x después del enésimo Node desde el final en la lista enlazada simple dada. Se garantiza que la lista contiene el Node n desde el final. También 1 <= n.
Ejemplos:
Input : list: 1->3->4->5
n = 4, x = 2
Output : 1->2->3->4->5
4th node from the end is 1 and
insertion has been done after this node.
Input : list: 10->8->3->12->5->18
n = 2, x = 11
Output : 10->8->3->12->5->11->18
Método 1 (usando la longitud de la lista): Encuentre la longitud de la lista enlazada, es decir, el número de Nodes en la lista. Que sea len . Ahora recorra la lista desde el primer Node hasta el (largo-n+1) Node desde el principio e inserte el nuevo Node después de este Node. Este método requiere dos recorridos de la lista.
Implementación:
C++
// C++ implementation to insert a node after
// the n-th node from the end
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
int data;
Node* next;
};
// function to get a new node
Node* getNode(int data)
{
// allocate memory for the node
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to insert a node after the
// nth node from the end
void insertAfterNthNode(Node* head, int n, int x)
{
// if list is empty
if (head == NULL)
return;
// get a new node for the value 'x'
Node* newNode = getNode(x);
Node* ptr = head;
int len = 0, i;
// find length of the list, i.e, the
// number of nodes in the list
while (ptr != NULL) {
len++;
ptr = ptr->next;
}
// traverse up to the nth node from the end
ptr = head;
for (i = 1; i <= (len - n); i++)
ptr = ptr->next;
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode->next = ptr->next;
ptr->next = newNode;
}
// function to print the list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
// Creating list 1->3->4->5
Node* head = getNode(1);
head->next = getNode(3);
head->next->next = getNode(4);
head->next->next->next = getNode(5);
int n = 4, x = 2;
cout << "Original Linked List: ";
printList(head);
insertAfterNthNode(head, n, x);
cout << "\nLinked List After Insertion: ";
printList(head);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
C
// C implementation to insert a node after
// the n-th node from the end
#include <stdio.h>
#include <stdlib.h>
// structure of a node
typedef struct Node {
int data;
struct Node* next;
} Node;
// function to get a new node
Node* getNode(int data)
{
// allocate memory for the node
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to insert a node after the
// nth node from the end
void insertAfterNthNode(Node* head, int n, int x)
{
// if list is empty
if (head == NULL)
return;
// get a new node for the value 'x'
Node* newNode = getNode(x);
Node* ptr = head;
int len = 0, i;
// find length of the list, i.e, the
// number of nodes in the list
while (ptr != NULL) {
len++;
ptr = ptr->next;
}
// traverse up to the nth node from the end
ptr = head;
for (i = 1; i <= (len - n); i++)
ptr = ptr->next;
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode->next = ptr->next;
ptr->next = newNode;
}
// function to print the list
void printList(Node* head)
{
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
}
// Driver program to test above
int main()
{
// Creating list 1->3->4->5
Node* head = getNode(1);
head->next = getNode(3);
head->next->next = getNode(4);
head->next->next->next = getNode(5);
int n = 4, x = 2;
printf("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
printf("\nLinked List After Insertion: ");
printList(head);
return 0;
}
// This code is contributed by Sania Kumari Gupta (kriSania804)
Java
// Java implementation to insert a node after
// the n-th node from the end
class GfG
{
// structure of a node
static class Node
{
int data;
Node next;
}
// function to get a new node
static Node getNode(int data)
{
// allocate memory for the node
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after the
// nth node from the end
static void insertAfterNthNode(Node head, int n, int x)
{
// if list is empty
if (head == null)
return;
// get a new node for the value 'x'
Node newNode = getNode(x);
Node ptr = head;
int len = 0, i;
// find length of the list, i.e, the
// number of nodes in the list
while (ptr != null)
{
len++;
ptr = ptr.next;
}
// traverse up to the nth node from the end
ptr = head;
for (i = 1; i <= (len - n); i++)
ptr = ptr.next;
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = ptr.next;
ptr.next = newNode;
}
// function to print the list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver code
public static void main(String[] args)
{
// Creating list 1->3->4->5
Node head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
int n = 4, x = 2;
System.out.print("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
System.out.println();
System.out.print("Linked List After Insertion: ");
printList(head);
}
}
// This code is contributed by prerna saini
Python3
# Python implementation to insert a node after
# the n-th node from the end
# Linked List node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# function to get a new node
def getNode(data) :
# allocate memory for the node
newNode = Node(0)
# put in the data
newNode.data = data
newNode.next = None
return newNode
# function to insert a node after the
# nth node from the end
def insertAfterNthNode(head, n, x) :
# if list is empty
if (head == None) :
return
# get a new node for the value 'x'
newNode = getNode(x)
ptr = head
len = 0
i = 0
# find length of the list, i.e, the
# number of nodes in the list
while (ptr != None) :
len = len + 1
ptr = ptr.next
# traverse up to the nth node from the end
ptr = head
i = 1
while ( i <= (len - n) ) :
ptr = ptr.next
i = i + 1
# insert the 'newNode' by making the
# necessary adjustment in the links
newNode.next = ptr.next
ptr.next = newNode
# function to print the list
def printList( head) :
while (head != None):
print(head.data ,end = " ")
head = head.next
# Driver code
# Creating list 1->3->4->5
head = getNode(1)
head.next = getNode(3)
head.next.next = getNode(4)
head.next.next.next = getNode(5)
n = 4
x = 2
print("Original Linked List: ")
printList(head)
insertAfterNthNode(head, n, x)
print()
print("Linked List After Insertion: ")
printList(head)
# This code is contributed by Arnab Kundu
C#
// C# implementation to insert a node after
// the n-th node from the end
using System;
class GfG
{
// structure of a node
public class Node
{
public int data;
public Node next;
}
// function to get a new node
static Node getNode(int data)
{
// allocate memory for the node
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after the
// nth node from the end
static void insertAfterNthNode(Node head, int n, int x)
{
// if list is empty
if (head == null)
return;
// get a new node for the value 'x'
Node newNode = getNode(x);
Node ptr = head;
int len = 0, i;
// find length of the list, i.e, the
// number of nodes in the list
while (ptr != null)
{
len++;
ptr = ptr.next;
}
// traverse up to the nth node from the end
ptr = head;
for (i = 1; i <= (len - n); i++)
ptr = ptr.next;
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = ptr.next;
ptr.next = newNode;
}
// function to print the list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver code
public static void Main(String[] args)
{
// Creating list 1->3->4->5
Node head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
int n = 4, x = 2;
Console.Write("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
Console.WriteLine();
Console.Write("Linked List After Insertion: ");
printList(head);
}
}
// This code has been contributed by 29AjayKumar
Javascript
<script>
// JavaScript implementation to
// insert a node after
// the n-th node from the end
// structure of a node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// function to get a new node
function getNode(data) {
// allocate memory for the node
var newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after the
// nth node from the end
function insertAfterNthNode(head , n , x) {
// if list is empty
if (head == null)
return;
// get a new node for the value 'x'
var newNode = getNode(x);
var ptr = head;
var len = 0, i;
// find length of the list, i.e, the
// number of nodes in the list
while (ptr != null) {
len++;
ptr = ptr.next;
}
// traverse up to the nth node from the end
ptr = head;
for (i = 1; i <= (len - n); i++)
ptr = ptr.next;
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = ptr.next;
ptr.next = newNode;
}
// function to print the list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver code
// Creating list 1->3->4->5
var head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
var n = 4, x = 2;
document.write("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
document.write();
document.write("<br/>Linked List After Insertion: ");
printList(head);
// This code contributed by gauravrajput1
</script>
Producción
Original Linked List: 1 3 4 5 Linked List After Insertion: 1 2 3 4 5
Complejidad temporal: O(n), donde n es el número de Nodes de la lista.
Espacio Auxiliar: O(1)
Método 2 (recorrido simple): este método utiliza dos punteros, uno es slow_ptr y el otro es fast_ptr . Primero mueva fast_ptr hasta el Node n desde el principio. Haga que slow_ptr apunte al primer Node de la lista. Ahora, mueva simultáneamente ambos punteros hasta que fast_ptr apunte al último Node. En este punto , slow_ptr apuntará al Node n desde el final. Inserte el nuevo Node después de este Node. Este método requiere un solo recorrido de la lista.
Implementación:
C++
// C++ implementation to insert a node after the
// nth node from the end
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
int data;
Node* next;
};
// function to get a new node
Node* getNode(int data)
{
// allocate memory for the node
Node* newNode = (Node*)malloc(sizeof(Node));
// put in the data
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to insert a node after the
// nth node from the end
void insertAfterNthNode(Node* head, int n, int x)
{
// if list is empty
if (head == NULL)
return;
// get a new node for the value 'x'
Node* newNode = getNode(x);
// Initializing the slow and fast pointers
Node* slow_ptr = head;
Node* fast_ptr = head;
// move 'fast_ptr' to point to the nth node
// from the beginning
for (int i = 1; i <= n - 1; i++)
fast_ptr = fast_ptr->next;
// iterate until 'fast_ptr' points to the
// last node
while (fast_ptr->next != NULL) {
// move both the pointers to the
// respective next nodes
slow_ptr = slow_ptr->next;
fast_ptr = fast_ptr->next;
}
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode->next = slow_ptr->next;
slow_ptr->next = newNode;
}
// function to print the list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above
int main()
{
// Creating list 1->3->4->5
Node* head = getNode(1);
head->next = getNode(3);
head->next->next = getNode(4);
head->next->next->next = getNode(5);
int n = 4, x = 2;
cout << "Original Linked List: ";
printList(head);
insertAfterNthNode(head, n, x);
cout << "\nLinked List After Insertion: ";
printList(head);
return 0;
}
Java
// Java implementation to
// insert a node after the
// nth node from the end
class GfG
{
// structure of a node
static class Node
{
int data;
Node next;
}
// function to get a new node
static Node getNode(int data)
{
// allocate memory for the node
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after
// the nth node from the end
static void insertAfterNthNode(Node head,
int n, int x)
{
// if list is empty
if (head == null)
return;
// get a new node for the value 'x'
Node newNode = getNode(x);
// Initializing the slow
// and fast pointers
Node slow_ptr = head;
Node fast_ptr = head;
// move 'fast_ptr' to point to the
// nth node from the beginning
for (int i = 1; i <= n - 1; i++)
fast_ptr = fast_ptr.next;
// iterate until 'fast_ptr' points
// to the last node
while (fast_ptr.next != null)
{
// move both the pointers to the
// respective next nodes
slow_ptr = slow_ptr.next;
fast_ptr = fast_ptr.next;
}
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = slow_ptr.next;
slow_ptr.next = newNode;
}
// function to print the list
static void printList(Node head)
{
while (head != null)
{
System.out.print(head.data + " ");
head = head.next;
}
}
// Driver code
public static void main(String[] args)
{
// Creating list 1->3->4->5
Node head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
int n = 4, x = 2;
System.out.println("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
System.out.println();
System.out.println("Linked List After Insertion: ");
printList(head);
}
}
// This code is contributed by
// Prerna Saini.
Python3
# Python3 implementation to insert a
# node after the nth node from the end
# Structure of a node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# Function to get a new node
def getNode(data):
# Allocate memory for the node
newNode = Node(data)
return newNode
# Function to insert a node after the
# nth node from the end
def insertAfterNthNode(head, n, x):
# If list is empty
if (head == None):
return
# Get a new node for the value 'x'
newNode = getNode(x)
# Initializing the slow and fast pointers
slow_ptr = head
fast_ptr = head
# Move 'fast_ptr' to point to the nth
# node from the beginning
for i in range(1, n):
fast_ptr = fast_ptr.next
# Iterate until 'fast_ptr' points to the
# last node
while (fast_ptr.next != None):
# Move both the pointers to the
# respective next nodes
slow_ptr = slow_ptr.next
fast_ptr = fast_ptr.next
# Insert the 'newNode' by making the
# necessary adjustment in the links
newNode.next = slow_ptr.next
slow_ptr.next = newNode
# Function to print the list
def printList(head):
while (head != None):
print(head.data, end = ' ')
head = head.next
# Driver code
if __name__=='__main__':
# Creating list 1.3.4.5
head = getNode(1)
head.next = getNode(3)
head.next.next = getNode(4)
head.next.next.next = getNode(5)
n = 4
x = 2
print("Original Linked List: ", end = '')
printList(head)
insertAfterNthNode(head, n, x)
print("\nLinked List After Insertion: ", end = '')
printList(head)
# This code is contributed by rutvik_56
C#
// C# implementation to
// insert a node after the
// nth node from the end
using System;
class GfG
{
// structure of a node
public class Node
{
public int data;
public Node next;
}
// function to get a new node
static Node getNode(int data)
{
// allocate memory for the node
Node newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after
// the nth node from the end
static void insertAfterNthNode(Node head,
int n, int x)
{
// if list is empty
if (head == null)
return;
// get a new node for the value 'x'
Node newNode = getNode(x);
// Initializing the slow
// and fast pointers
Node slow_ptr = head;
Node fast_ptr = head;
// move 'fast_ptr' to point to the
// nth node from the beginning
for (int i = 1; i <= n - 1; i++)
fast_ptr = fast_ptr.next;
// iterate until 'fast_ptr' points
// to the last node
while (fast_ptr.next != null)
{
// move both the pointers to the
// respective next nodes
slow_ptr = slow_ptr.next;
fast_ptr = fast_ptr.next;
}
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = slow_ptr.next;
slow_ptr.next = newNode;
}
// function to print the list
static void printList(Node head)
{
while (head != null)
{
Console.Write(head.data + " ");
head = head.next;
}
}
// Driver code
public static void Main()
{
// Creating list 1->3->4->5
Node head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
int n = 4, x = 2;
Console.WriteLine("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
Console.WriteLine();
Console.WriteLine("Linked List After Insertion: ");
printList(head);
}
}
/* This code contributed by PrinciRaj1992 */
Javascript
<script>
// JavaScript implementation to
// insert a node after the
// nth node from the end
// structure of a node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// function to get a new node
function getNode(data) {
// allocate memory for the node
var newNode = new Node();
// put in the data
newNode.data = data;
newNode.next = null;
return newNode;
}
// function to insert a node after
// the nth node from the end
function insertAfterNthNode(head, n, x) {
// if list is empty
if (head == null) return;
// get a new node for the value 'x'
var newNode = getNode(x);
// Initializing the slow
// and fast pointers
var slow_ptr = head;
var fast_ptr = head;
// move 'fast_ptr' to point to the
// nth node from the beginning
for (var i = 1; i <= n - 1; i++)
fast_ptr = fast_ptr.next;
// iterate until 'fast_ptr' points
// to the last node
while (fast_ptr.next != null) {
// move both the pointers to the
// respective next nodes
slow_ptr = slow_ptr.next;
fast_ptr = fast_ptr.next;
}
// insert the 'newNode' by making the
// necessary adjustment in the links
newNode.next = slow_ptr.next;
slow_ptr.next = newNode;
}
// function to print the list
function printList(head) {
while (head != null) {
document.write(head.data + " ");
head = head.next;
}
}
// Driver code
// Creating list 1->3->4->5
var head = getNode(1);
head.next = getNode(3);
head.next.next = getNode(4);
head.next.next.next = getNode(5);
var n = 4,
x = 2;
document.write("Original Linked List: ");
printList(head);
insertAfterNthNode(head, n, x);
document.write("<br>");
document.write("Linked List After Insertion:");
printList(head);
</script>
Producción
Original Linked List: 1 3 4 5 Linked List After Insertion: 1 2 3 4 5
Complejidad de tiempo: O(n) , donde n es el número de Nodes en la lista.
Espacio Auxiliar: O(1)
Método 3 (Enfoque recursivo):
- Recorra la lista recursivamente hasta llegar al último Node.
- mientras retrocede, inserte el Node en la posición deseada.
Implementación:
C++
// C++ implementation to insert a node after the
// nth node from the end
#include <bits/stdc++.h>
using namespace std;
// structure of a node
struct Node {
int data;
Node* next;
};
// function to get a new node
Node* getNode(int data)
{
// allocate memory for the node
Node* newNode = new Node();
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// function to insert a node after the
// nth node from the end
void insertAfterNthNode(Node* head, int x, int& n)
{
// Base case
if (head == NULL)
return;
// recursively traverse till the last node
insertAfterNthNode(head->next, x, n);
// condition to insert the node after nth node from end
if (--n == 0) {
// create a node with the given value
Node* temp = getNode(x);
// update the next pointer to point next node in the
// list
temp->next = head->next;
// make sure head points to newly inserted node
head->next = temp;
}
}
// function to print the list
void printList(Node* head)
{
while (head != NULL) {
cout << head->data << " ";
head = head->next;
}
}
// Driver program to test above functions
int main()
{
// Creating list 1->3->4->5
Node* head = getNode(1);
head->next = getNode(3);
head->next->next = getNode(4);
head->next->next->next = getNode(5);
int n = 4, x = 2;
cout << "Original Linked List: ";
printList(head);
insertAfterNthNode(head, x, n);
cout << "\nLinked List After Insertion: ";
printList(head);
return 0;
}
// This code is contributed by Upendra
Producción
Original Linked List: 1 3 4 5 Linked List After Insertion: 1 2 3 4 5
Complejidad temporal: O(n), donde n es el número de Nodes de la lista.
Espacio Auxiliar: O(n)
Este artículo es una contribución de Ayush Jauhari . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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