Cómo insertar un Node en una lista enlazada individualmente en una posición dada usando recursividad

Posted on by Rudeus Greyrat

Dada una lista enlazada individualmente como lista , una posición y un Node , la tarea es insertar ese elemento en la lista enlazada dada en una posición dada usando recursividad .

Ejemplos: 

Entrada: lista = 1->2->3->4->5->6->7, Node = (val=100,siguiente=nulo), posición = 4 
Salida: 1->2->3-> 100->4->5->6->7
Explicación: Aquí el Node con valor 100 se inserta en la 4ª posición. Inicialmente, en la cuarta posición, el valor es 4. Ahora, cuando se inserta 100 en la cuarta posición, todo el valor a partir de 4 cambiará 1 posición a su derecha. Esto se puede visualizar de la siguiente manera:

1->2->3-> 4 ->5->6->7
1->2->3-> 100 ->4->5->6->7

Entrada: lista = 1->2->3->100->4->5->6->7, Node = (val=101,siguiente=nulo), posición = 1  
Salida: 10->1-> 2->3->100->4->5->6->7

 

Solución:

Habrá 3 casos :

  1. Insertar un Node en la primera posición de la lista enlazada
    • Enfoque: Siga los pasos que se mencionan a continuación:
      1. Cree un Node temporal.
      2. Ahora inserte el Node temporal antes de la cabeza y cambie el puntero de la cabeza para señalar el Node temporal.
  2. Inserte un Node entre el primer y el último Node de la lista vinculada
    • Enfoque: Siga los pasos que se mencionan a continuación:
      1. Llame a la función recursiva para llegar a la posición deseada.
      2. Si la posición es mayor que la longitud de la lista, la inserción no es posible.
      3. De lo contrario, inserte el nuevo Node en la posición deseada.
  3. Insertar un Node al final de la lista enlazada
    • Enfoque: Siga los pasos que se mencionan a continuación:
      1. Mover recursivamente al final de la lista enlazada.
      2. Inserte el nuevo Node al final de la lista.

Relación de recurrencia: T(n) = T(n-1) + c

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

C++

// C++ code to insert a node
// at a given position
// in singly linked list
#include <bits/stdc++.h>
#define null nullptr
 
using namespace std;
 
// Structure of the node of linked list
struct node {
    int item;
    node* nxt;
    node(int item, node* t)
    {
        this->item = item;
        (*this).nxt = t;
    }
};
 
// Function to insert a node
// at the first position
node* insertAtFirst(node*& listHead, node* x)
{
    node* temp = listHead;
    x->nxt = temp;
    listHead = temp = x;
    return temp;
}
 
// Function to insert a node
// at the last position
node* insertAtEnd(node* listHead, node* x)
{
    if (listHead->nxt == null) {
        listHead->nxt = x;
        return listHead;
    }
    listHead->nxt
      = insertAtEnd(listHead->nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
node* insertInBetween(node* temp,
                      node* x, int pos)
{
    if (pos == 2) {
        if (temp != null) {
            x->nxt = temp->nxt;
            temp->nxt = x;
        }
        return temp;
    }
    if (temp == null) {
        return temp;
    }
    temp->nxt
      = insertInBetween(temp->nxt, x, --pos);
}
 
// Printing through recursion
void print(node* head)
{
    if (head == null) {
        return;
    }
    cout << head->item << " ";
    print(head->nxt);
}
 
// Driver code
int main()
{
    node* head = new node(1, 0);
 
    // Creating a linked list of length 15
    for (int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, 0));
 
    // Insert node with value 100
    // at 4th position
    insertInBetween(head,
                    new node(100, 0), 4);
 
    // Insert node with value 101
    // at 200th position
    insertInBetween(head,
                    new node(101, 0), 200);
 
    // Insert node with value 100
    // at 1st position
    insertAtFirst(head, new node(100, 0));
 
    // Insert node with value 100
    // at the end position
    insertAtEnd(head, new node(100, 0));
 
    // Printing the new linked list
    print(head);
    return 0;
}

Java

// Java code to insert a node at a given
//position in singly linked list
class GFG{
 
// Structure of the node of linked list
static class node
{
    int item;
    node nxt;
     
    node(int item, node t)
    {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
static node insertAtFirst(node listHead, node x)
{
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
static node insertAtEnd(node listHead, node x)
{
    if (listHead.nxt == null)
    {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
static node insertInBetween(node temp, node x,
                            int pos)
{
    if (pos == 2)
    {
        if (temp != null)
        {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null)
    {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
static void print(node head)
{
    if (head == null)
    {
        return;
    }
    System.out.print(head.item + " ");
    print(head.nxt);
}
 
// Driver code
public static void main(String[] args)
{
    node head = new node(1, null);
 
    // Creating a linked list of length 15
    for(int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, null));
 
    // Insert node with value 100
    // at 4th position
    head = insertInBetween(head,
                    new node(100, null), 4);
 
    // Insert node with value 101
    // at 200th position
    head = insertInBetween(head,
                    new node(101, null), 200);
 
    // Insert node with value 100
    // at 1st position
    head = insertAtFirst(head, new node(100, null));
 
    // Insert node with value 100
    // at the end position
    head = insertAtEnd(head, new node(100, null));
 
    // Printing the new linked list
    print(head);
}
}
 
// This code is contributed by shikhasingrajput

Python3

# Python code to insert a node in a
# given Singly Linked List (recursively)
 
class Node:
 
    # Structure of the node.
    def __init__(self, item):
        self.item = item
        self.nxt = None
     
 
# Function to insert a node at
# first position in the given
# Linked List
def insertAtFirst(listHead, item):
    new = Node(item)
    new.nxt = listHead
    return new
# Time Complexity - O(1)
 
 
# Function to insert a node
# at the end of the given
# Linked List (recursively)
def insertAtEnd(listHead, item):
    if listHead is None:
        new = Node(item)
        return new
 
    if listHead.nxt is None:
        new = Node(item)
        listHead.nxt = new
        return listHead
     
    insertAtEnd(listHead.nxt, item)
    return listHead
# Time Complexity - O(n)
 
 
# Function to insert a node
# at a specific position in
# the given Linked List (recursively)
def insertInBetween(temp, item, pos):
 
    # if head is None and given position is greater than 0
    if temp is None and pos>0:
        return temp
 
    # if the node is to be added at first position
    if pos==0:
        new = Node(item)
        new.nxt = temp
        return new
     
    # if the node is to be added at second position
    if pos==1:
        new = Node(item)
        new.nxt = temp.nxt
        temp.nxt = new
        return temp
    insertInBetween(temp.nxt, item, pos-1)
    return temp
# Time Complexity - O(i)
 
 
# Function to print the Linked List through Recursion
def printll(head):
    if head==None:
        return
    print(head.item, end=' ')
    printll(head.nxt)
# Time Complexity - O(n)
# where n is the length of the linked list
 
 
# Driver code
if __name__=='__main__':
     
    head = None
 
    # Creating a Linked List of length 15
    for i in range(1, 16):
        head = insertAtEnd(head, i)
     
    # Insert node with value 100
    # at 4th position
    head = insertInBetween(head, 100, 3)
 
    # Insert node with value 101
    # at 200th position
    head = insertInBetween(head, 101, 200)
 
    # Insert node with value 100
    # at 1st position
    head = insertAtFirst(head, 100)
 
    # Insert node with value 100
    # at the end position
    head = insertAtEnd(head, 100)
 
    # Printing the new linked list
    printll(head)
 
# This code is contributed by Harshit Rathore

C#

// C# code to insert a node at a given
//position in singly linked list
using System;
 
public class GFG{
 
// Structure of the node of linked list
class node
{
    public int item;
    public node nxt;
     
    public node(int item, node t)
    {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
static node insertAtFirst(node listHead, node x)
{
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
static node insertAtEnd(node listHead, node x)
{
    if (listHead.nxt == null)
    {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
static node insertInBetween(node temp, node x,
                            int pos)
{
    if (pos == 2)
    {
        if (temp != null)
        {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null)
    {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
static void print(node head)
{
    if (head == null)
    {
        return;
    }
    Console.Write(head.item + " ");
    print(head.nxt);
}
 
// Driver code
public static void Main(String[] args)
{
    node head = new node(1, null);
 
    // Creating a linked list of length 15
    for(int i = 2; i < 16; i++)
        insertAtEnd(head, new node(i, null));
 
    // Insert node with value 100
    // at 4th position
    head = insertInBetween(head,
                    new node(100, null), 4);
 
    // Insert node with value 101
    // at 200th position
    head = insertInBetween(head,
                    new node(101, null), 200);
 
    // Insert node with value 100
    // at 1st position
    head = insertAtFirst(head, new node(100, null));
 
    // Insert node with value 100
    // at the end position
    head = insertAtEnd(head, new node(100, null));
 
    // Printing the new linked list
    print(head);
}
}
 
// This code is contributed by shikhasingrajput

Javascript

<script>
// Javascript code to insert a node at a given
// position in singly linked list
 
// Structure of the node of linked list
class node {
 
    constructor(item, t) {
        this.item = item;
        this.nxt = t;
    }
};
 
// Function to insert a node
// at the first position
function insertAtFirst(listHead, x) {
    x.nxt = listHead;
    listHead = null;
    listHead = x;
    return listHead;
}
 
// Function to insert a node
// at the last position
function insertAtEnd(listHead, x) {
    if (listHead.nxt == null) {
        listHead.nxt = x;
        return listHead;
    }
    listHead.nxt = insertAtEnd(listHead.nxt, x);
    return listHead;
}
 
// Function to insert a node
// in between first and last
function insertInBetween(temp, x, pos) {
    if (pos == 2) {
        if (temp != null) {
            x.nxt = temp.nxt;
            temp.nxt = x;
        }
        return temp;
    }
    if (temp == null) {
        return temp;
    }
    temp.nxt = insertInBetween(temp.nxt, x, --pos);
    return temp;
}
 
// Printing through recursion
function _print(head) {
    if (head == null) {
        return;
    }
    document.write(head.item + " ");
    _print(head.nxt);
}
 
// Driver code
let head = new node(1, null);
 
// Creating a linked list of length 15
for (let i = 2; i < 16; i++)
    insertAtEnd(head, new node(i, null));
 
// Insert node with value 100
// at 4th position
head = insertInBetween(head,
    new node(100, null), 4);
 
// Insert node with value 101
// at 200th position
head = insertInBetween(head,
    new node(101, null), 200);
 
// Insert node with value 100
// at 1st position
head = insertAtFirst(head, new node(100, null));
 
// Insert node with value 100
// at the end position
head = insertAtEnd(head, new node(100, null));
 
// Printing the new linked list
_print(head);
 
    // This code is contributed by Saurabh Jaiswal
</script>
Producción

100 1 2 3 100 4 5 6 7 8 9 10 11 12 13 14 15 100

Complejidad de tiempo: O(N) donde N es el tamaño de la lista enlazada
Espacio auxiliar: O(N) donde N es el tamaño de la lista enlazada

Un enfoque más simple del código C++ anterior:

C++

#include <iostream>
using namespace std;
 
class Node {
public:
    int data;
    Node* next;
 
    Node(int data)
    {
        this->data = data;
        next = NULL;
    }
};
 
Node* insertatk(Node* head, int k, int data)
{
    if (head == NULL)
        return new Node(data);
 
      if (k == 1) {
        Node* newnode = new Node(data);
        newnode->next = head;
        head = newnode;
          return head;
    }
    else
        head->next=insertatk(head->next, k-1, data);//we do k-1 so as to reach the required place
   
      return head;
}
 
void print(Node* head)
{
    Node* temp = head;
    while (temp != NULL) {
        cout << temp->data << " ";
        temp = temp->next;
    }
    cout << "\n";
}
 
int main()
{
      //inserting nodes and connecting them at the same time
    Node* head = new Node(1);
    Node* n1 = new Node(2);
    head->next = n1;
    Node* n2 = new Node(3);
    n1->next = n2;
    Node* n3 = new Node(4);
    n2->next = n3;
    Node* n4 = new Node(5);
    n3->next = n4;
    Node* n5 = new Node(6);
    n4->next = n5;
      Node* n6 = new Node(7);
    n5->next = n6;
    n6->next = NULL;
 
    int k = 4;
    int data = 100;
   
    print(insertatk(head, k, data));
    return 0;
}
Producción

1 2 3 100 4 5 6 7

Publicación traducida automáticamente

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