Dada una lista enlazada. La tarea es eliminar el Node N del final de la lista enlazada.
Ejemplos:
Entrada: 1->2->3->4->5, N = 2
Salida: 1->2->3->5Entrada: 7->8->4->3->2, N = 1
Salida: 7->8->4->3
Requisitos previos:
1. Eliminar un Node de la lista vinculada.
2. Encuentre el Node n desde el final de la lista enlazada
Enfoque:
Eliminar el Node B desde el último es básicamente lo mismo que eliminar (longitud-B+1) desde el principio. En nuestro enfoque, primero, evaluamos la longitud de la lista enlazada, luego verificamos
- Si longitud < B, entonces no podemos eliminar el Node
- Si longitud = B, entonces regresa cabeza->siguiente
- Si la longitud > B, significa que tenemos que eliminar el Node intermedio, eliminaremos este Node y haremos que su Node anterior apunte al siguiente Node del Node eliminado.
C
// C program to delete nth node from last
#include<stdio.h>
#include<stdlib.h>
// Structure of node
struct Node {
int data;
struct Node* next;
};
// Function to insert node in a linked list
struct Node* create(struct Node* head, int x)
{
struct Node *temp, *ptr = head;
temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = x;
temp->next = NULL;
if (head == NULL)
head = temp;
else {
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = temp;
}
return head;
}
// Function to remove nth node from last
struct Node* removeNthFromEnd(struct Node* head, int B)
{
// To store length of the linked list
int len = 0;
struct Node* tmp = head;
while (tmp != NULL) {
len++;
tmp = tmp->next;
}
// B > length, then we can't remove node
if (B > len)
{
printf( "Length of the linked list is %d",len );
printf( " we can't remove %dth node from the",B);
printf(" linked list\n");
return head;
}
// We need to remove head node
else if (B == len) {
// Return head->next
return head->next;
}
else
{
// Remove len - B th node from starting
int diff = len - B;
struct Node* prev= NULL;
struct Node* curr = head;
for(int i = 0;i < diff;i++){
prev = curr;
curr = curr->next;
}
prev->next = curr->next;
return head;
}
}
// This function prints contents of linked
// list starting from the given node
void display(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ",temp->data);
temp = temp->next;
}
printf("\n");
}
// Driver code
int main()
{
struct Node* head = NULL;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
int n = 2;
printf("Linked list before modification: \n");
display(head);
head = removeNthFromEnd(head, 2);
printf("Linked list after modification: \n");
display(head);
return 0;
}
C++
// CPP program to delete nth node from last
#include <bits/stdc++.h>
using namespace std;
// Structure of node
struct Node {
int data;
struct Node* next;
};
// Function to insert node in a linked list
struct Node* create(struct Node* head, int x)
{
struct Node *temp, *ptr = head;
temp = new Node();
temp->data = x;
temp->next = NULL;
if (head == NULL)
head = temp;
else {
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = temp;
}
return head;
}
// Function to remove nth node from last
Node* removeNthFromEnd(Node* head, int B)
{
// To store length of the linked list
int len = 0;
Node* tmp = head;
while (tmp != NULL) {
len++;
tmp = tmp->next;
}
// B > length, then we can't remove node
if (B > len)
{
cout << "Length of the linked list is " << len;
cout << " we can't remove "<< B << "th node from the";
cout << " linked list\n";
return head;
}
// We need to remove head node
else if (B == len) {
// Return head->next
return head->next;
}
else
{
// Remove len - B th node from starting
int diff = len - B;
Node* prev= NULL;
Node* curr = head;
for(int i = 0;i < diff;i++){
prev = curr;
curr = curr->next;
}
prev->next = curr->next;
return head;
}
}
// This function prints contents of linked
// list starting from the given node
void display(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Driver code
int main()
{
struct Node* head = NULL;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
int n = 2;
cout << "Linked list before modification: \n";
display(head);
head = removeNthFromEnd(head, 2);
cout << "Linked list after modification: \n";
display(head);
return 0;
}
Java
// Java program to delete nth node from last
class GFG
{
// Structure of node
static class Node
{
int data;
Node next;
};
// Function to insert node in a linked list
static Node create(Node head, int x)
{
Node temp, ptr = head;
temp = new Node();
temp.data = x;
temp.next = null;
if (head == null)
head = temp;
else
{
while (ptr.next != null)
{
ptr = ptr.next;
}
ptr.next = temp;
}
return head;
}
// Function to remove nth node from last
static Node removeNthFromEnd(Node head, int B)
{
// To store length of the linked list
int len = 0;
Node tmp = head;
while (tmp != null)
{
len++;
tmp = tmp.next;
}
// B > length, then we can't remove node
if (B > len)
{
System.out.print("Length of the linked list is " + len);
System.out.print(" we can't remove "+ B +
"th node from the");
System.out.print(" linked list\n");
return head;
}
// We need to remove head node
else if (B == len)
{
// Return head.next
return head.next;
}
else
{
// Remove len - B th node from starting
int diff = len - B;
Node prev= null;
Node curr = head;
for(int i = 0; i < diff; i++)
{
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
return head;
}
}
// This function prints contents of linked
// list starting from the given node
static void display(Node head)
{
Node temp = head;
while (temp != null)
{
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
// Driver code
public static void main(String[] args)
{
Node head = null;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
int n = 2;
System.out.print("Linked list before modification: \n");
display(head);
head = removeNthFromEnd(head, 2);
System.out.print("Linked list after modification: \n");
display(head);
}
}
// This code is contributed by Rajput-Ji
Python3
# Python3 program to delete nth node from last
class Node:
# Function to initialise the node object
def __init__(self, data):
self.data = data # Assign data
self.next = None # Initialize next as null
class LinkedList:
# Function to initialize head
def __init__(self):
self.head = None
# Function to add node at the end
def create(self, x):
new_node = Node(x)
if self.head is None:
self.head = new_node
return
last = self.head
while last.next:
last = last.next
last.next = new_node
# This function prints contents of linked
# list starting from the given node
def display(self):
temp = self.head
while temp:
print(temp.data, end = " ")
temp = temp.next
# Function to remove nth node from last
def removeNthFromEnd(head, k):
# the function uses two pointer method
first = head
second = head
count = 1
while count <= k:
second = second.next
count += 1
if second is None:
head.value = head.next.value
head.next = head.next.next
return
while second.next is not None:
first = first.next
second = second.next
first.next = first.next.next
# Driver code
# val list contains list of values
val = [1, 2, 3, 4, 5]
k = 2
ll = LinkedList()
for i in val:
ll.create(i)
print("Linked list before modification:");
ll.display()
removeNthFromEnd(ll.head, k)
print("\nLinked list after modification:");
ll.display()
# This code is contributed by Dhinesh
C#
// C# program to delete nth node from last
using System;
class GFG
{
// Structure of node
class Node
{
public int data;
public Node next;
};
// Function to insert node in a linked list
static Node create(Node head, int x)
{
Node temp, ptr = head;
temp = new Node();
temp.data = x;
temp.next = null;
if (head == null)
head = temp;
else
{
while (ptr.next != null)
{
ptr = ptr.next;
}
ptr.next = temp;
}
return head;
}
// Function to remove nth node from last
static Node removeNthFromEnd(Node head, int B)
{
// To store length of the linked list
int len = 0;
Node tmp = head;
while (tmp != null)
{
len++;
tmp = tmp.next;
}
// B > length, then we can't remove node
if (B > len)
{
Console.Write("Length of the linked list is " + len);
Console.Write(" we can't remove " + B +
"th node from the");
Console.Write(" linked list\n");
return head;
}
// We need to remove head node
else if (B == len)
{
// Return head.next
return head.next;
}
else
{
// Remove len - B th node from starting
int diff = len - B;
Node prev= null;
Node curr = head;
for(int i = 0; i < diff; i++)
{
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
return head;
}
}
// This function prints contents of linked
// list starting from the given node
static void display(Node head)
{
Node temp = head;
while (temp != null)
{
Console.Write(temp.data + " ");
temp = temp.next;
}
Console.Write("\n");
}
// Driver code
public static void Main(String[] args)
{
Node head = null;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
Console.Write("Linked list before modification: \n");
display(head);
head = removeNthFromEnd(head, 2);
Console.Write("Linked list after modification: \n");
display(head);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// javascript program to delete nth node from last // Structure of node
class Node {
constructor() {
this.data = 0;
this.next = null;
}
}
// Function to insert node in a linked list
function create(head , x) {
var temp, ptr = head;
temp = new Node();
temp.data = x;
temp.next = null;
if (head == null)
head = temp;
else {
while (ptr.next != null) {
ptr = ptr.next;
}
ptr.next = temp;
}
return head;
}
// Function to remove nth node from last
function removeNthFromEnd(head , B) {
// To store length of the linked list
var len = 0;
var tmp = head;
while (tmp != null) {
len++;
tmp = tmp.next;
}
// B > length, then we can't remove node
if (B > len) {
document.write("Length of the linked list is " + len);
document.write(" we can't remove " + B + "th node from the");
document.write(" linked list\n");
return head;
}
// We need to remove head node
else if (B == len) {
// Return head.next
return head.next;
}
else {
// Remove len - B th node from starting
var diff = len - B;
var prev = null;
var curr = head;
for (i = 0; i < diff; i++) {
prev = curr;
curr = curr.next;
}
prev.next = curr.next;
return head;
}
}
// This function prints contents of linked
// list starting from the given node
function display(head) {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
// Driver code
var head = null;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
var n = 2;
document.write("Linked list before modification: <br/>");
display(head);
head = removeNthFromEnd(head, 2);
document.write("Linked list after modification: <br/>");
display(head);
// This code contributed by Rajput-Ji
</script>
Producción
Linked list before modification: 1 2 3 4 5 Linked list after modification: 1 2 3 5
Complejidad de tiempo: O(N)
Espacio Auxiliar: O(N)
Otro enfoque:
Enfoque de dos punteros
Eliminar el Node Bth desde el último es básicamente lo mismo que eliminar (longitud-B+1) desde el principio. En nuestro enfoque, definiremos 2 punteros, puntero rápido y puntero lento.
Algoritmo:
- Tome dos Nodes slowPtr y fastPtr, de modo que next apunte a la cabeza
- Tome un Node para almacenar la cabeza, inicialmente es un Node ficticio (inicio), y el siguiente Node apuntará a la cabeza. El Node ficticio se toma para manejar el caso extremo donde B = N (tamaño de LinkedList)
- Comience a atravesar hasta que el puntero rápido alcance el Node n.
- Comience a recorrer en un paso ambos punteros hasta que los punteros rápidos lleguen al final
- Cuando finalice el recorrido, elimine el siguiente Node a slowPtr
- Devolver el siguiente de inicio
C++
// CPP program to delete nth node from last
#include <bits/stdc++.h>
using namespace std;
// Structure of node
struct Node {
int data;
struct Node* next;
};
// Function to insert node in a linked list
struct Node* create(struct Node* head, int x)
{
struct Node *temp, *ptr = head;
temp = new Node();
temp->data = x;
temp->next = NULL;
if (head == NULL)
head = temp;
else {
while (ptr->next != NULL) {
ptr = ptr->next;
}
ptr->next = temp;
}
return head;
}
// Function to remove nth node from last
Node* removeNthFromEnd(Node* head, int B)
{
Node *start = new Node();
start -> next = head;
Node* fastPtr = start;
Node* slowPtr = start;
// Traverse the LinkedList B times
for(int i = 0; i < B; i++){
fastPtr = fastPtr->next;
}
//Increase the slow pointer
while(fastPtr->next != NULL)
{
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
//Deletion step
slowPtr->next = slowPtr->next->next;
//Return head
return start->next;
}
// This function prints contents of linked
// list starting from the given node
void display(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
// Driver code
int main()
{
struct Node* head = NULL;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
int n = 2;
cout << "Linked list before modification: \n";
display(head);
head = removeNthFromEnd(head, 2);
cout << "Linked list after modification: \n";
display(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
C
// C program to delete nth node from last
#include <stdio.h>
#include <stdlib.h>
// Structure of node
typedef struct Node {
int data;
struct Node* next;
} Node;
// Function to insert node in a linked list
Node* create(Node* head, int x)
{
Node* ptr = head;
Node* temp = (Node*)malloc(sizeof(Node));
temp->data = x;
temp->next = NULL;
if (head == NULL)
head = temp;
else {
while (ptr->next != NULL)
ptr = ptr->next;
ptr->next = temp;
}
return head;
}
// Function to remove nth node from last
Node* removeNthFromEnd(Node* head, int B)
{
Node* start = (Node*)malloc(sizeof(Node));
start->next = head;
Node* fastPtr = start;
Node* slowPtr = start;
// Traverse the LinkedList B times
for (int i = 0; i < B; i++)
fastPtr = fastPtr->next;
// Increase the slow pointer
while (fastPtr->next != NULL) {
fastPtr = fastPtr->next;
slowPtr = slowPtr->next;
}
// Deletion step
slowPtr->next = slowPtr->next->next;
// Return head
return start->next;
}
// This function prints contents of linked
// list starting from the given node
void display(struct Node* head)
{
struct Node* temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
// Driver code
int main()
{
struct Node* head = NULL;
head = create(head, 1);
head = create(head, 2);
head = create(head, 3);
head = create(head, 4);
head = create(head, 5);
int n = 2;
printf("Linked list before modification: \n");
display(head);
head = removeNthFromEnd(head, 2);
printf("Linked list after modification: \n");
display(head);
return 0;
}
// This code is contributed by Aditya Kumar (adityakumar129)
Java
// Java program to delete nth node from last
import java.io.*;
class GFG {
// Structure of node
class Node {
int data;
Node next;
}
// Function to insert node in a linked list
public Node create(Node head, int x)
{
Node temp = new Node();
Node ptr = head;
temp.data = x;
temp.next = null;
if (head == null) {
head = temp;
}
else {
while (ptr.next != null) {
ptr = ptr.next;
}
ptr.next = temp;
}
return head;
}
// Function to remove nth node from last
public Node removeNthFromEnd(Node head, int B)
{
Node start = new Node();
start.next = head;
Node fastPtr = start;
Node slowPtr = start;
// Traverse the LinkedList B times
for (int i = 0; i < B; i++) {
fastPtr = fastPtr.next;
}
// Increase the slow pointer
while (fastPtr.next != null) {
fastPtr = fastPtr.next;
slowPtr = slowPtr.next;
}
// Deletion step
slowPtr.next = slowPtr.next.next;
// Return head
return start.next;
}
// This function prints contents of linked list starting
// from the given node
public void display(Node head)
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
public static void main(String[] args)
{
GFG l = new GFG();
Node head = null;
head = l.create(head, 1);
head = l.create(head, 2);
head = l.create(head, 3);
head = l.create(head, 4);
head = l.create(head, 5);
System.out.println(
"Linked List before modification: ");
l.display(head);
head = l.removeNthFromEnd(head, 2);
System.out.println(
"Linked List after modification: ");
l.display(head);
}
}
// This code is contributed by lokesh (lokeshmvs21).
Producción
Linked list before modification: 1 2 3 4 5 Linked list after modification: 1 2 3 5
Complejidad de tiempo : O(N) donde N no es ningún Node en la lista enlazada
Complejidad espacial : O (1) porque usa variables constantes