Dada una lista enlazada y un número entero N , la tarea es eliminar el Node N del final de la lista enlazada dada.
Ejemplos:
Entrada: 2 -> 3 -> 1 -> 7 -> NULL, N = 1
Salida:
La lista vinculada creada es:
2 3 1 7
La lista vinculada después de la eliminación es:
2 3 1Entrada: 1 -> 2 -> 3 -> 4 -> NULL, N = 4
Salida:
La lista vinculada creada es:
1 2 3 4
La lista vinculada después de la eliminación es:
2 3 4
Intuición:
Sean K los Nodes totales en la lista enlazada.
Observación: El Node N desde el final es (K-N+1) el Node desde el principio.
Entonces, el problema se simplifica a que tenemos que encontrar (K-N+1) el Node desde el principio.
- Una forma de hacerlo es encontrar la longitud (K) de la lista enlazada en un paso y luego, en el segundo paso, mover (K-N+1) paso desde el principio hasta llegar al Node N desde el final.
- Para hacerlo de una pasada. Tomemos el primer puntero y avancemos N pasos desde el principio. Ahora el primer puntero está a (K-N+1) pasos del último Node, que es el mismo número de pasos que requiere el segundo puntero para moverse desde el principio hasta llegar al N -ésimo Node desde el final.
Acercarse:
- Toma dos punteros; el primero apuntará al encabezado de la lista enlazada y el segundo apuntará al Node N desde el principio.
- Ahora siga incrementando ambos punteros en uno al mismo tiempo hasta que el segundo apunte al último Node de la lista enlazada.
- Después de las operaciones del paso anterior, el primer puntero debe apuntar al Node N desde el final ahora . Por lo tanto, elimine el Node al que apunta el primer puntero.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation of the approach
#include <bits/stdc++.h>
using namespace std;
class LinkedList {
public:
// Linked list Node
class Node {
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
};
// Head of list
Node* head;
// Function to delete the nth node from the end of the
// given linked list
Node* deleteNode(int key)
{
// We will be using this pointer for holding address
// temporarily while we delete the node
Node* temp;
// First pointer will point to the head of the
// linked list
Node* first = head;
// Second pointer will point to the Nth node from
// the beginning
Node* second = head;
for (int i = 0; i < key; i++) {
// If count of nodes in the given linked list is <= N
if (second->next == NULL) {
// If count = N i.e. delete the head node
if (i == key - 1) {
temp = head;
head = head->next;
free(temp);
}
return head;
}
second = second->next;
}
// Increment both the pointers by one until second
// pointer reaches the end
while (second->next != NULL) {
first = first->next;
second = second->next;
}
// First must be pointing to the Nth node from the
// end by now So, delete the node first is pointing to
temp = first->next;
first->next = first->next->next;
free(temp);
return head;
}
// Function to insert a new Node at front of the list
Node* push(int new_data)
{
Node* new_node = new Node(new_data);
new_node->next = head;
head = new_node;
return head;
}
// Function to print the linked list
void printList()
{
Node* tnode = head;
while (tnode != NULL) {
cout << (tnode->data) << (" ");
tnode = tnode->next;
}
}
};
// Driver code
int main()
{
LinkedList* llist = new LinkedList();
llist->head = llist->push(7);
llist->head = llist->push(1);
llist->head = llist->push(3);
llist->head = llist->push(2);
cout << ("Created Linked list is:\n");
llist->printList();
int N = 1;
llist->head = llist->deleteNode(N);
cout << ("\nLinked List after Deletion is:\n");
llist->printList();
}
// This code is contributed by Sania Kumari Gupta
C
/* C program to merge two sorted linked lists */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
/* Link list node */
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* deleteNode(Node* head, int key)
{
// We will be using this pointer for holding address
// temporarily while we delete the node
Node* temp;
// First pointer will point to the head of the linked
// list
Node* first = head;
// Second pointer will point to the Nth node from the
// beginning
Node* second = head;
for (int i = 0; i < key; i++) {
// If count of nodes in the given linked list is <=N
if (second->next == NULL) {
// If count = N i.e. delete the head node
if (i == key - 1) {
temp = head;
head = head->next;
free(temp);
}
return head;
}
second = second->next;
}
// Increment both the pointers by one until
// second pointer reaches the end
while (second->next != NULL) {
first = first->next;
second = second->next;
}
// First must be pointing to the Nth node from the end
// by now So, delete the node first is pointing to
temp = first->next;
first->next = first->next->next;
free(temp);
return head;
}
/* Function to insert a node at the beginning of the
linked list */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = (Node*)malloc(sizeof(Node));
/* put in the data */
new_node->data = new_data;
/* link the old list off the new node */
new_node->next = (*head_ref);
/* move the head to point to the new node */
(*head_ref) = new_node;
}
/* Function to print nodes in a given linked list */
void printList(struct Node* node)
{
while (node != NULL) {
printf("%d ", node->data);
node = node->next;
}
}
// Driver program
int main()
{
struct Node* head = NULL;
push(&head, 7);
push(&head, 1);
push(&head, 3);
push(&head, 2);
printf("Created Linked list is:\n");
printList(head);
int n = 1;
deleteNode(head, n);
printf("\nLinked List after Deletion is:\n");
printList(head);
return 0;
}
// This code is contributed by Sania Kumari Gupta
Java
// Java implementation of the approach
class LinkedList {
// Head of list
Node head;
// Linked list Node
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
// Function to delete the nth node from
// the end of the given linked list
void deleteNode(int key)
{
// First pointer will point to
// the head of the linked list
Node first = head;
// Second pointer will point to the
// Nth node from the beginning
Node second = head;
for (int i = 0; i < key; i++) {
// If count of nodes in the given
// linked list is <= N
if (second.next == null) {
// If count = N i.e. delete the head node
if (i == key - 1)
head = head.next;
return;
}
second = second.next;
}
// Increment both the pointers by one until
// second pointer reaches the end
while (second.next != null) {
first = first.next;
second = second.next;
}
// First must be pointing to the
// Nth node from the end by now
// So, delete the node first is pointing to
first.next = first.next.next;
}
// Function to insert a new Node at front of the list
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to print the linked list
public void printList()
{
Node tnode = head;
while (tnode != null) {
System.out.print(tnode.data + " ");
tnode = tnode.next;
}
}
// Driver code
public static void main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(7);
llist.push(1);
llist.push(3);
llist.push(2);
System.out.println("\nCreated Linked list is:");
llist.printList();
int N = 1;
llist.deleteNode(N);
System.out.println("\nLinked List after Deletion is:");
llist.printList();
}
}
Python3
# Python3 implementation of the approach
class Node:
def __init__(self, new_data):
self.data = new_data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
# createNode and make linked list
def push(self, new_data):
new_node = Node(new_data)
new_node.next = self.head
self.head = new_node
def deleteNode(self, n):
first = self.head
second = self.head
for i in range(n):
# If count of nodes in the
# given list is less than 'n'
if(second.next == None):
# If index = n then
# delete the head node
if(i == n - 1):
self.head = self.head.next
return self.head
second = second.next
while(second.next != None):
second = second.next
first = first.next
first.next = first.next.next
def printList(self):
tmp_head = self.head
while(tmp_head != None):
print(tmp_head.data, end = ' ')
tmp_head = tmp_head.next
# Driver Code
llist = LinkedList()
llist.push(7)
llist.push(1)
llist.push(3)
llist.push(2)
print("Created Linked list is:")
llist.printList()
llist.deleteNode(1)
print("\nLinked List after Deletion is:")
llist.printList()
# This code is contributed by RaviParkash
C#
// C# implementation of the approach
using System;
public class LinkedList
{
// Head of list
public Node head;
// Linked list Node
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d;
next = null;
}
}
// Function to delete the nth node from
// the end of the given linked list
void deleteNode(int key)
{
// First pointer will point to
// the head of the linked list
Node first = head;
// Second pointer will point to the
// Nth node from the beginning
Node second = head;
for (int i = 0; i < key; i++)
{
// If count of nodes in the given
// linked list is <= N
if (second.next == null)
{
// If count = N i.e. delete the head node
if (i == key - 1)
head = head.next;
return;
}
second = second.next;
}
// Increment both the pointers by one until
// second pointer reaches the end
while (second.next != null)
{
first = first.next;
second = second.next;
}
// First must be pointing to the
// Nth node from the end by now
// So, delete the node first is pointing to
first.next = first.next.next;
}
// Function to insert a new Node at front of the list
public void push(int new_data)
{
Node new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to print the linked list
public void printList()
{
Node tnode = head;
while (tnode != null)
{
Console.Write(tnode.data + " ");
tnode = tnode.next;
}
}
// Driver code
public static void Main(String[] args)
{
LinkedList llist = new LinkedList();
llist.push(7);
llist.push(1);
llist.push(3);
llist.push(2);
Console.WriteLine("\nCreated Linked list is:");
llist.printList();
int N = 1;
llist.deleteNode(N);
Console.WriteLine("\nLinked List after Deletion is:");
llist.printList();
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript implementation of the approach
// Head of list
var head;
// Linked list Node
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
// Function to delete the nth node from
// the end of the given linked list
function deleteNode(key) {
// First pointer will point to
// the head of the linked list
var first = head;
// Second pointer will point to the
// Nth node from the beginning
var second = head;
for (i = 0; i < key; i++) {
// If count of nodes in the given
// linked list is <= N
if (second.next == null) {
// If count = N i.e. delete the head node
if (i == key - 1)
head = head.next;
return;
}
second = second.next;
}
// Increment both the pointers by one until
// second pointer reaches the end
while (second.next != null) {
first = first.next;
second = second.next;
}
// First must be pointing to the
// Nth node from the end by now
// So, delete the node first is pointing to
first.next = first.next.next;
}
// Function to insert a new Node at front of the list
function push(new_data) {
var new_node = new Node(new_data);
new_node.next = head;
head = new_node;
}
// Function to print the linked list
function printList() {
var tnode = head;
while (tnode != null) {
document.write(tnode.data + " ");
tnode = tnode.next;
}
}
// Driver code
push(7);
push(1);
push(3);
push(2);
document.write("\nCreated Linked list is:<br/>");
printList();
var N = 1;
deleteNode(N);
document.write("<br/>Linked List after Deletion is:<br/>");
printList();
// This code is contributed by todaysgaurav
</script>
Producción
Created Linked list is: 2 3 1 7 Linked List after Deletion is: 2 3 1
ya cubrimos la versión iterativa anterior,
ahora veamos también su enfoque recursivo ,
Enfoque recursivo:
1) Cree un Node ficticio y cree un enlace desde el Node ficticio al Node principal. es decir, dummy->next = head
2) Luego, usaremos la pila de recursividad para realizar un seguimiento de los elementos que se envían en las llamadas de recurrencia.
3) Mientras extraemos los elementos de la pila de recursión, disminuiremos la N (posición del Node de destino desde el final de la lista vinculada), es decir, N = N-1.
4) Cuando alcancemos (N==0) eso significa que hemos llegado al Node de destino,
5) Pero aquí está el problema, para eliminar el Node de destino requerimos su Node anterior,
6) Entonces, ahora nos detendremos cuando (N ==-1) es decir, llegamos al Node anterior.
7) Ahora es muy sencillo eliminar el Node utilizando el Node anterior->siguiente = Nodeanterior->siguiente->siguiente.
C++
// C++ implementation of the approach
// Code is contributed by Paras Saini
#include <bits/stdc++.h>
using namespace std;
class LinkedList {
public:
int val;
LinkedList* next;
LinkedList()
{
this->next = NULL;
this->val = 0;
}
LinkedList(int val)
{
this->next = NULL;
this->val = val;
}
LinkedList* addNode(int val)
{
if (this == NULL) {
return new LinkedList(val);
}
else {
LinkedList* ptr = this;
while (ptr->next) {
ptr = ptr->next;
}
ptr->next = new LinkedList(val);
return this;
}
}
void removeNthNodeFromEndHelper(LinkedList* head,
int& n)
{
if (!head)
return;
// Adding the elements in the recursion
// stack
removeNthNodeFromEndHelper(head->next, n);
// Popping the elements from recursion stack
n -= 1;
// If we reach the previous of target node
if (n == -1){
LinkedList* temp = head->next;
head->next = head->next->next;
free (temp);
}
}
LinkedList* removeNthNodeFromEnd(int n)
{
// return NULL if we have NULL head or only
// one node.
if (!this or !this->next)
return NULL;
// Create a dummy node and point its next to
// head.
LinkedList* dummy = new LinkedList();
dummy->next = this;
// Call function to remove Nth node from end
removeNthNodeFromEndHelper(dummy, n);
// Return new head i.e, dummy->next
return dummy->next;
}
void printLinkedList()
{
if (!this) {
cout << "Empty List\n";
return;
}
LinkedList* ptr = this;
while (ptr) {
cout << ptr->val << " ";
ptr = ptr->next;
}
cout << endl;
}
};
class TestCase {
private:
void printOutput(LinkedList* head)
{
// Output:
if (!head)
cout << "Empty Linked List\n";
else
head->printLinkedList();
}
void testCase1()
{
LinkedList* head = new LinkedList(1);
head = head->addNode(2);
head = head->addNode(3);
head = head->addNode(4);
head = head->addNode(5);
head->printLinkedList(); // Print: 1 2 3 4 5
head = head->removeNthNodeFromEnd(2);
printOutput(head); // Output: 1 2 3 5
}
void testCase2()
{
// Important Edge Case, where linkedList [1]
// and n=1,
LinkedList* head = new LinkedList(1);
head->printLinkedList(); // Print: 1
head = head->removeNthNodeFromEnd(2);
printOutput(head); // Output: Empty Linked List
}
void testCase3()
{
LinkedList* head = new LinkedList(1);
head = head->addNode(2);
head->printLinkedList(); // Print: 1 2
head = head->removeNthNodeFromEnd(1);
printOutput(head); // Output: 1
}
public:
void executeTestCases()
{
testCase1();
testCase2();
testCase3();
}
};
int main()
{
TestCase testCase;
testCase.executeTestCases();
return 0;
}
Producción
1 2 3 4 5 1 2 3 5 1 Empty Linked List 1 2 1
Enfoque de dos punteros: punteros lentos y rápidos
Este problema se puede resolver utilizando el enfoque de dos punteros como se muestra a continuación:
- Tome dos punteros: rápido y lento. E inicializa sus valores como Node principal.
- Iterar puntero rápido hasta el valor de n.
- Ahora, inicie la iteración del puntero rápido hasta el valor Ninguno de la lista vinculada. Además, iterar el puntero lento.
- Por lo tanto, una vez que el puntero rápido llegue al final, el puntero lento alcanzará el Node que desea eliminar.
- Reemplace el siguiente Node del puntero lento con el siguiente Node del puntero lento.
C++
// C++ code for the deleting a node from end using two
// pointer approach
#include <iostream>
using namespace std;
class LinkedList {
public:
// structure of a node
class Node {
public:
int data;
Node* next;
Node(int d)
{
data = d;
next = NULL;
}
};
// Head node
Node* head;
// Function for inserting a node at the beginning
void push(int data)
{
Node* new_node = new Node(data);
new_node->next = head;
head = new_node;
}
// Function to display the nodes in the list.
void display()
{
Node* temp = head;
while (temp != NULL) {
cout << temp->data << endl;
temp = temp->next;
}
}
// Function to delete the nth node from the end.
void deleteNthNodeFromEnd(Node* head, int n)
{
Node* fast = head;
Node* slow = head;
for (int i = 0; i < n; i++) {
fast = fast->next;
}
if (fast == NULL) {
return;
}
while (fast->next != NULL) {
fast = fast->next;
slow = slow->next;
}
slow->next = slow->next->next;
return;
}
};
int main()
{
LinkedList* l = new LinkedList();
// Create a list 1->2->3->4->5->NULL
l->push(5);
l->push(4);
l->push(3);
l->push(2);
l->push(1);
cout << "***** Linked List Before deletion *****"
<< endl;
l->display();
cout << "************** Delete nth Node from the End "
"*****"
<< endl;
l->deleteNthNodeFromEnd(l->head, 2);
cout << "*********** Linked List after Deletion *****"
<< endl;
l->display();
return 0;
}
// This code is contributed by lokesh (lokeshmvs21).
Java
// Java code for deleting a node from the end using two
// Pointer Approach
class GFG {
class Node {
int data;
Node next;
Node(int data)
{
this.data = data;
this.next = null;
}
}
Node head;
// Function to insert node at the beginning of the list.
public void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
// Function to print the nodes in the linked list.
public void display()
{
Node temp = head;
while (temp != null) {
System.out.println(temp.data);
temp = temp.next;
}
}
public void deleteNthNodeFromEnd(Node head, int n)
{
Node fast = head;
Node slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
return;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return;
}
public static void main(String[] args)
{
GFG l = new GFG();
// Create a list 1->2->3->4->5->NULL
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);
System.out.println(
"***** Linked List Before deletion *****");
l.display();
System.out.println(
"************** Delete nth Node from the End *****");
l.deleteNthNodeFromEnd(l.head, 2);
System.out.println(
"*********** Linked List after Deletion *****");
l.display();
}
}
// This code is contributed by lokesh (lokeshmvs21).
Python
class Node:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = None
def push(self, data):
new_node = Node(data)
new_node.next = self.head
self.head = new_node
def display(self):
temp = self.head
while temp != None:
print(temp.data)
temp = temp.next
def deleteNthNodeFromEnd(self, head, n):
fast = head
slow = head
for _ in range(n):
fast = fast.next
if not fast:
return head.next
while fast.next:
fast = fast.next
slow = slow.next
slow.next = slow.next.next
return head
if __name__ == '__main__':
l = LinkedList()
l.push(5)
l.push(4)
l.push(3)
l.push(2)
l.push(1)
print('***** Linked List Before deletion *****')
l.display()
print('************** Delete nth Node from the End *****')
l.deleteNthNodeFromEnd(l.head, 2)
print('*********** Linked List after Deletion *****')
l.display()
C#
// C# code for deleting a node from the end using two
// Pointer Approach
using System;
public class GFG {
public class Node {
public int data;
public Node next;
public Node(int data)
{
this.data = data;
this.next = null;
}
}
Node head;
void push(int data)
{
Node new_node = new Node(data);
new_node.next = head;
head = new_node;
}
void display()
{
Node temp = head;
while (temp != null) {
Console.WriteLine(temp.data);
temp = temp.next;
}
}
public void deleteNthNodeFromEnd(Node head, int n)
{
Node fast = head;
Node slow = head;
for (int i = 0; i < n; i++) {
fast = fast.next;
}
if (fast == null) {
return;
}
while (fast.next != null) {
fast = fast.next;
slow = slow.next;
}
slow.next = slow.next.next;
return;
}
static public void Main()
{
// Code
GFG l = new GFG();
// Create a list 1->2->3->4->5->NULL
l.push(5);
l.push(4);
l.push(3);
l.push(2);
l.push(1);
Console.WriteLine(
"***** Linked List Before deletion *****");
l.display();
Console.WriteLine(
"************** Delete nth Node from the End *****");
l.deleteNthNodeFromEnd(l.head, 2);
Console.WriteLine(
"*********** Linked List after Deletion *****");
l.display();
}
}
// This code is contributed by lokesh(lokeshmvs21).
Javascript
<script>
class Node{
constructor(data){
this.data = data
this.next = null
}
}
class LinkedList{
constructor(){
this.head = null
}
push(data){
let new_node = new Node(data)
new_node.next =this.head
this.head = new_node
}
display(){
let temp =this.head
while(temp != null){
document.write(temp.data,"</br>")
temp = temp.next
}
}
deleteNthNodeFromEnd(head, n){
let fast = head
let slow = head
for(let i=0;i<n;i++){
fast = fast.next
}
if(!fast)
return head.next
while(fast.next){
fast = fast.next
slow = slow.next
}
slow.next = slow.next.next
return head
}
}
// driver code
let l = new LinkedList()
l.push(5)
l.push(4)
l.push(3)
l.push(2)
l.push(1)
document.write('***** Linked List Before deletion *****',"</br>")
l.display()
document.write('************** Delete nth Node from the End *****',"</br>")
l.deleteNthNodeFromEnd(l.head, 2)
document.write('*********** Linked List after Deletion *****',"</br>")
l.display()
// This code is contributed by shinjanpatra
</script>
Producción
***** Linked List Before deletion ***** 1 2 3 4 5 ************** Delete nth Node from the End ***** *********** Linked List after Deletion ***** 1 2 3 5
Complejidad temporal: O(n)
Complejidad espacial: O(1) usando espacio constante