Elimine los Nodes Kth del principio y el final de una lista enlazada

Posted on by Rudeus Greyrat

Dada una Lista Vinculada individual y un número entero K que denota la posición de una Lista Vinculada, la tarea es eliminar el K -ésimo Node desde el principio y el final de la Lista Vinculada .

Ejemplos: 

Entrada: 1 → 2 → 3 → 4 → 5 → 6, K = 3
Salida : 1 → 2 → 5 → 6
Explicación: Nodes eliminados: 3, 4

Entrada: 1 → 2 → 3 → 4 → 5 → 6 , K = 1
Salida: 2 → 3 → 4 → 5

Entrada: 1 → 2 → 3 → 4 → 5 → 6, K = 4
Salida: 1 → 2 → 5 → 6

Enfoque: Siga los pasos para resolver el problema

  1. Inicialice dos punteros , rápido y lento , para recorrer la lista enlazada .
  2. Apunte ambos Nodes al encabezado de la Lista enlazada .
  3. Iterar usando el puntero rápido , hasta que rápido apunte a (K – 1) el Node desde el principio.
  4. Mientras atraviesa, mantenga firstPrev para almacenar el Node anterior del puntero rápido .
  5. Ahora, incremente los punteros lentos y rápidos en un Node en cada iteración, hasta que fast->next sea igual a NULL .
  6. Mientras atraviesa, mantenga secondPrev para almacenar el Node anterior del puntero lento .
  7. Elimine ambos Nodes de la lista enlazada, utilizando los punteros firstPrev y secondPrev .
  8. Imprima la lista enlazada actualizada.

A continuación se muestra la implementación del enfoque anterior:

C++14

// C++ implementation of the above approach
 
#include <bits/stdc++.h>
#include <iostream>
using namespace std;
 
// Structure of a
// Linked list Node
struct Node {
    int data;
    struct Node* next;
};
 
// Function to insert a new node
// at the front of the Linked List
void push(struct Node** head_ref, int new_data)
{
    struct Node* new_node
        = (struct Node*)malloc(sizeof(struct Node));
    new_node->data = new_data;
    new_node->next = (*head_ref);
    (*head_ref) = new_node;
}
 
// Function to print the Linked List
void printList(struct Node* node)
{
    // while node is not NULL
    while (node != NULL) {
        cout << node->data << " ";
        node = node->next;
    }
    cout << endl;
}
 
// Function to delete nodes from
// both ends of a Linked List
Node* DeleteNodesfromBothEnds(struct Node** head_ref, int k)
{
    // Empty List
    if (head_ref == NULL)
        return *head_ref;
 
    // Represent nodes that remove
    // the next node of each
    Node* firstPrev = NULL;
    Node* secondPrev = NULL;
 
    Node* fast = *head_ref;
 
    // copy of head_ref
    Node* head = *head_ref;
 
    // Move fast to (k - 1)
    // nodes ahead of slow
    for (int i = 0; i < k - 1; ++i) {
        firstPrev = fast;
        fast = fast->next;
    }
 
    Node* slow = *head_ref;
 
    // Iterate until fast reaches
    // end of the Linked List
    while (fast != NULL && fast->next != NULL) {
        secondPrev = slow;
        slow = slow->next;
        fast = fast->next;
    }
 
    // Remove first node
    if (firstPrev == secondPrev) {
 
        if (firstPrev == NULL) {
 
            // Remove the head node
            head = head->next;
        }
        else {
 
            // Remove the middle Node
            firstPrev->next = firstPrev->next->next;
        }
    }
    else if (firstPrev != NULL && secondPrev != NULL
             && (firstPrev->next == secondPrev
                 || secondPrev->next == firstPrev)) {
 
        // If firstPrev comes first
        if (firstPrev->next == secondPrev)
            firstPrev->next = secondPrev->next->next;
 
        // If secondPrev comes first
        else
            secondPrev->next = firstPrev->next->next;
    }
    else {
 
        // Remove the head node
        if (firstPrev == NULL) {
            head = head->next;
        }
        else {
 
            // Removethe first Node
            firstPrev->next = firstPrev->next->next;
        }
 
        // Remove the head node
        if (secondPrev == NULL) {
            head = head->next;
        }
        else {
 
            // Remove the second Node
            secondPrev->next = secondPrev->next->next;
        }
    }
    return head;
}
 
// Driver code
int main()
{
 
    // Given Linked List
    struct Node* head = NULL;
    push(&head, 6);
    push(&head, 5);
    push(&head, 4);
    push(&head, 3);
    push(&head, 2);
    push(&head, 1);
 
    // Given position
    int K = 3;
 
    printList(head);
 
    // Function call to delete nodes
    // from both ends of Linked List
    head = DeleteNodesfromBothEnds(&head, K);
 
    // Print the updated Linked List
    printList(head);
 
    return 0;
}

Java

// Java implementation of the approach
import java.io.*;
 
public class Simple {
 
    // Stores the head and tail
    // of the Linked List
    Node head = null;
    Node tail = null;
 
    // Structure of a
    // Linked list Node
    class Node {
        int data;
        Node next;
 
        Node(int d)
        {
            data = d;
            next = null;
        }
    }
 
    // Function to delete nodes from
    // both ends of a Linked List
    Node DeleteNodesfromBothEnds(int k)
    {
        // Empty List
        if (head == null)
            return head;
 
        // Represent nodes that remove
        // the next node of each
        Node firstPrev = null, secondPrev = null;
 
        Node fast = head;
 
        // Move fast to (k - 1)
        // nodes ahead of slow
        for (int i = 0; i < k - 1; ++i) {
            firstPrev = fast;
            fast = fast.next;
        }
 
        Node slow = head;
 
        // Iterate until fast reaches
        // end of the Linked List
        while (fast != null
               && fast.next != null) {
            secondPrev = slow;
            slow = slow.next;
            fast = fast.next;
        }
 
        // Remove first node
        if (firstPrev == secondPrev) {
 
            if (firstPrev == null) {
 
                // Remove the head node
                head = head.next;
            }
            else {
 
                // Remove the middle Node
                firstPrev.next
                    = firstPrev.next.next;
            }
        }
        else if (firstPrev != null && secondPrev != null
                 && (firstPrev.next == secondPrev
                     || secondPrev.next == firstPrev)) {
 
            // If firstPrev comes first
            if (firstPrev.next == secondPrev)
                firstPrev.next
                    = secondPrev.next.next;
 
            // If secondPrev comes first
            else
                secondPrev.next
                    = firstPrev.next.next;
        }
        else {
 
            // Remove the head node
            if (firstPrev == null) {
                head = head.next;
            }
            else {
 
                // Removethe first Node
                firstPrev.next
                    = firstPrev.next.next;
            }
 
            // Remove the head node
            if (secondPrev == null) {
                head = head.next;
            }
            else {
 
                // Remove the second Node
                secondPrev.next
                    = secondPrev.next.next;
            }
        }
 
        return head;
    }
 
    // Function to insert a new node
    // at the end of the Linked List
    public void push(int new_data)
    {
        Node new_node = new Node(new_data);
 
        if (head == null) {
            head = new_node;
            tail = new_node;
        }
        else {
            tail.next = new_node;
            tail = new_node;
        }
    }
 
    // Function to print the Linked List
    public void printList()
    {
        Node tnode = head;
 
        // while tnode is not NULL
        while (tnode != null) {
            System.out.print(tnode.data + " ");
            tnode = tnode.next;
        }
    }
 
    // Driver Code
    public static void main(String[] args)
    {
 
        // Given Linked List
        Simple llist = new Simple();
        llist.push(1);
        llist.push(2);
        llist.push(3);
        llist.push(4);
        llist.push(5);
        llist.push(6);
 
        // Given position
        int K = 3;
 
        // Function call to delete nodes
        // from both ends of Linked List
        llist.DeleteNodesfromBothEnds(K);
 
        // Print the updated Linked List
        llist.printList();
    }
}

C#

// C# implementation of the approach
using System;
 
public class Simple {
 
  // Stores the head and tail
  // of the Linked List
  public Node head = null;
  public Node tail = null;
 
  // Structure of a
  // Linked list Node
  public class Node {
    public int data;
    public Node next;
 
    public Node(int d)
    {
      data = d;
      next = null;
    }
  }
 
  // Function to delete nodes from
  // both ends of a Linked List
  public Node DeleteNodesfromBothEnds(int k)
  {
    // Empty List
    if (head == null)
      return head;
 
    // Represent nodes that remove
    // the next node of each
    Node firstPrev = null, secondPrev = null;
 
    Node fast = head;
 
    // Move fast to (k - 1)
    // nodes ahead of slow
    for (int i = 0; i < k - 1; ++i) {
      firstPrev = fast;
      fast = fast.next;
    }
 
    Node slow = head;
 
    // Iterate until fast reaches
    // end of the Linked List
    while (fast != null
           && fast.next != null) {
      secondPrev = slow;
      slow = slow.next;
      fast = fast.next;
    }
 
    // Remove first node
    if (firstPrev == secondPrev) {
 
      if (firstPrev == null) {
 
        // Remove the head node
        head = head.next;
      }
      else {
 
        // Remove the middle Node
        firstPrev.next
          = firstPrev.next.next;
      }
    }
    else if (firstPrev != null && secondPrev != null
             && (firstPrev.next == secondPrev
                 || secondPrev.next == firstPrev)) {
 
      // If firstPrev comes first
      if (firstPrev.next == secondPrev)
        firstPrev.next
        = secondPrev.next.next;
 
      // If secondPrev comes first
      else
        secondPrev.next
        = firstPrev.next.next;
    }
    else {
 
      // Remove the head node
      if (firstPrev == null) {
        head = head.next;
      }
      else {
 
        // Removethe first Node
        firstPrev.next
          = firstPrev.next.next;
      }
 
      // Remove the head node
      if (secondPrev == null) {
        head = head.next;
      }
      else {
 
        // Remove the second Node
        secondPrev.next
          = secondPrev.next.next;
      }
    }
 
    return head;
  }
 
  // Function to insert a new node
  // at the end of the Linked List
  public void push(int new_data)
  {
    Node new_node = new Node(new_data);
 
    if (head == null) {
      head = new_node;
      tail = new_node;
    }
    else {
      tail.next = new_node;
      tail = new_node;
    }
  }
 
  // Function to print the Linked List
  public void printList()
  {
    Node tnode = head;
 
    // while tnode is not NULL
    while (tnode != null) {
      Console.Write(tnode.data + " ");
      tnode = tnode.next;
    }
  }
 
  // Driver Code
  public static void Main(String[] args)
  {
 
    // Given Linked List
    Simple llist = new Simple();
    llist.push(1);
    llist.push(2);
    llist.push(3);
    llist.push(4);
    llist.push(5);
    llist.push(6);
 
    // Given position
    int K = 3;
 
    // Function call to delete nodes
    // from both ends of Linked List
    llist.DeleteNodesfromBothEnds(K);
 
    // Print the updated Linked List
    llist.printList();
  }
}
 
// This code contributed by shikhasingrajput

Javascript

<script>
 
// Javascript implementation of the above approach
 
// Structure of a
// Linked list Node
class Node {
 
    constructor()
    {
        this.data = 0;
        this.next = null;
    }
};
 
// Function to insert a new node
// at the front of the Linked List
function push(head_ref, new_data)
{
    var new_node = new Node();
    new_node.data = new_data;
    new_node.next = (head_ref);
    (head_ref) = new_node;
    return head_ref;
}
 
// Function to print the Linked List
function printList(node)
{
    // while node is not null
    while (node != null) {
        document.write( node.data + " ");
        node = node.next;
    }
    document.write("<br>");
}
 
// Function to delete nodes from
// both ends of a Linked List
function DeleteNodesfromBothEnds(head_ref, k)
{
    // Empty List
    if (head_ref == null)
        return head_ref;
 
    // Represent nodes that remove
    // the next node of each
    var firstPrev = null;
    var secondPrev = null;
 
    var fast = head_ref;
 
    // copy of head_ref
    var head = head_ref;
 
    // Move fast to (k - 1)
    // nodes ahead of slow
    for (var i = 0; i < k - 1; ++i) {
        firstPrev = fast;
        fast = fast.next;
    }
 
    var slow = head_ref;
 
    // Iterate until fast reaches
    // end of the Linked List
    while (fast != null && fast.next != null) {
        secondPrev = slow;
        slow = slow.next;
        fast = fast.next;
    }
 
    // Remove first node
    if (firstPrev == secondPrev) {
 
        if (firstPrev == null) {
 
            // Remove the head node
            head = head.next;
        }
        else {
 
            // Remove the middle Node
            firstPrev.next = firstPrev.next.next;
        }
    }
    else if (firstPrev != null && secondPrev != null
             && (firstPrev.next == secondPrev
                 || secondPrev.next == firstPrev)) {
 
        // If firstPrev comes first
        if (firstPrev.next == secondPrev)
            firstPrev.next = secondPrev.next.next;
 
        // If secondPrev comes first
        else
            secondPrev.next = firstPrev.next.next;
    }
    else {
 
        // Remove the head node
        if (firstPrev == null) {
            head = head.next;
        }
        else {
 
            // Removethe first Node
            firstPrev.next = firstPrev.next.next;
        }
 
        // Remove the head node
        if (secondPrev == null) {
            head = head.next;
        }
        else {
 
            // Remove the second Node
            secondPrev.next = secondPrev.next.next;
        }
    }
    return head;
}
 
// Driver code
// Given Linked List
var head = null;
head = push(head, 6);
head = push(head, 5);
head = push(head, 4);
head = push(head, 3);
head = push(head, 2);
head = push(head, 1);
// Given position
var K = 3;
printList(head);
// Function call to delete nodes
// from both ends of Linked List
head = DeleteNodesfromBothEnds(head, K);
// Print the updated Linked List
printList(head);
 
// This code is contributed by rrrtnx.
</script>
Producción

1 2 3 4 5 6 
1 2 5 6

Complejidad de tiempo: O(N)
Complejidad de espacio: O(1)

Publicación traducida automáticamente

Artículo escrito por Kingash 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 *