Eliminar el Node N del final de la lista enlazada

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->5

Entrada: 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. 
     
 

Complete Interview Preparation - GFG 

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: 

  1. Tome dos Nodes slowPtr y fastPtr, de modo que next apunte a la cabeza
  2. 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)
  3. Comience a atravesar hasta que el puntero rápido alcance el Node n.
  4. Comience a recorrer en un paso ambos punteros hasta que los punteros rápidos lleguen al final
  5. Cuando finalice el recorrido, elimine el siguiente Node a slowPtr
  6. 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

Publicación traducida automáticamente

Artículo escrito por md1844 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *