Dada una lista enlazada individualmente, a partir del segundo Node, elimine todos los Nodes alternativos de la misma. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5 entonces su función debería convertirla a 1->3->5, y si la lista enlazada dada es 1->2-> 3->4 luego conviértalo a 1->3.
Método 1 (iterativo)
Realice un seguimiento del anterior del Node que se eliminará. Primero, cambie el siguiente enlace del Node anterior y muévase iterativamente al siguiente Node.
C++
// C++ program to remove alternate
// nodes of a linked list
#include <bits/stdc++.h>
using namespace std;
/* A linked list node */
class Node
{
public:
int data;
Node *next;
};
/* deletes alternate nodes
of a list starting with head */
void deleteAlt(Node *head)
{
if (head == NULL)
return;
/* Initialize prev and node to be deleted */
Node *prev = head;
Node *node = head->next;
while (prev != NULL && node != NULL)
{
/* Change next link of previous node */
prev->next = node->next;
delete(node); // delete the node
/* Update prev and node */
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(Node** head_ref, int new_data)
{
/* allocate node */
Node* new_node = new 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(Node *node)
{
while (node != NULL)
{
cout<< node->data<<" ";
node = node->next;
}
}
/* Driver code */
int main()
{
/* Start with the empty list */
Node* head = NULL;
/* Using push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
cout<<"List before calling deleteAlt() \n";
printList(head);
deleteAlt(head);
cout<<"\nList after calling deleteAlt() \n";
printList(head);
return 0;
}
// This code is contributed by rathbhupendra
C
// C program to remove alternate nodes of a linked list
#include<stdio.h>
#include<stdlib.h>
/* A linked list node */
struct Node
{
int data;
struct Node *next;
};
/* deletes alternate nodes of a list starting with head */
void deleteAlt(struct Node *head)
{
if (head == NULL)
return;
/* Initialize prev and node to be deleted */
struct Node *prev = head;
struct Node *node = head->next;
while (prev != NULL && node != NULL)
{
/* Change next link of previous node */
prev->next = node->next;
/* Free memory */
free(node);
/* Update prev and node */
prev = prev->next;
if (prev != NULL)
node = prev->next;
}
}
/* UTILITY FUNCTIONS TO TEST fun1() and fun2() */
/* Given a reference (pointer to pointer) to the head
of a list and an int, push a new node on the front
of the list. */
void push(struct Node** head_ref, int new_data)
{
/* allocate node */
struct Node* new_node =
(struct Node*) malloc(sizeof(struct 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 to test above functions */
int main()
{
/* Start with the empty list */
struct Node* head = NULL;
/* Using push() to construct below list
1->2->3->4->5 */
push(&head, 5);
push(&head, 4);
push(&head, 3);
push(&head, 2);
push(&head, 1);
printf("\nList before calling deleteAlt() \n");
printList(head);
deleteAlt(head);
printf("\nList after calling deleteAlt() \n");
printList(head);
return 0;
}
Java
// Java program to delete alternate nodes of a linked list
class LinkedList {
Node head; // head of list
/* Linked list Node*/
class Node {
int data;
Node next;
Node(int d)
{
data = d;
next = null;
}
}
void deleteAlt()
{
if (head == null)
return;
Node node = head;
while (node != null && node.next != null) {
/* Change next link of next node */
node.next = node.next.next;
/*Update ref node to new alternate node */
node = node.next;
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}
/* Driver program to test above functions */
public static void main(String args[])
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is 1->2->3->4->5->null */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
System.out.println(
"Linked List before calling deleteAlt() ");
llist.printList();
llist.deleteAlt();
System.out.println(
"Linked List after calling deleteAlt() ");
llist.printList();
}
}
/* This code is contributed by Rajat Mishra */
Python3
# Python3 program to remove alternate
# nodes of a linked list
import math
# A linked list node
class Node:
def __init__(self, data):
self.data = data
self.next = None
# deletes alternate nodes
# of a list starting with head
def deleteAlt(head):
if (head == None):
return
# Initialize prev and node to be deleted
prev = head
now = head.next
while (prev != None and now != None):
# Change next link of previous node
prev.next = now.next
# Free memory
now = None
# Update prev and node
prev = prev.next
if (prev != None):
now = prev.next
# UTILITY FUNCTIONS TO TEST fun1() and fun2()
# Given a reference (pointer to pointer) to the head
# of a list and an , push a new node on the front
# of the list.
def push(head_ref, new_data):
# allocate node
new_node = Node(new_data)
# 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
return head_ref
# Function to print nodes in a given linked list
def printList(node):
while (node != None):
print(node.data, end = " ")
node = node.next
# Driver code
if __name__=='__main__':
# Start with the empty list
head = None
# Using head=push() to construct below list
# 1.2.3.4.5
head = push(head, 5)
head = push(head, 4)
head = push(head, 3)
head = push(head, 2)
head = push(head, 1)
print("List before calling deleteAlt() ")
printList(head)
deleteAlt(head)
print("\nList after calling deleteAlt() ")
printList(head)
# This code is contributed by Srathore
C#
// C# program to delete alternate
// nodes of a linked list
using System;
public class LinkedList
{
Node head; // head of list
/* Linked list Node*/
public class Node
{
public int data;
public Node next;
public Node(int d)
{
data = d; next = null;
}
}
void deleteAlt()
{
if (head == null)
return;
Node prev = head;
Node now = head.next;
while (prev != null && now != null)
{
/* Change next link of previous node */
prev.next = now.next;
/* Free node */
now = null;
/*Update prev and now */
prev = prev.next;
if (prev != null)
now = prev.next;
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
public void push(int new_data)
{
/* 1 & 2: Allocate the Node &
Put in the data*/
Node new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
void printList()
{
Node temp = head;
while(temp != null)
{
Console.Write(temp.data+" ");
temp = temp.next;
}
Console.WriteLine();
}
/* Driver code*/
public static void Main(String []args)
{
LinkedList llist = new LinkedList();
/* Constructed Linked List is
1->2->3->4->5->null */
llist.push(5);
llist.push(4);
llist.push(3);
llist.push(2);
llist.push(1);
Console.WriteLine("Linked List before" +
"calling deleteAlt() ");
llist.printList();
llist.deleteAlt();
Console.WriteLine("Linked List after" +
"calling deleteAlt() ");
llist.printList();
}
}
// This code has been contributed
// by 29AjayKumar
Javascript
<script>
// Javascript program to delete alternate
// nodes of a linked list
var head; // head of list
/* Linked list Node */
class Node {
constructor(val) {
this.data = val;
this.next = null;
}
}
function deleteAlt() {
if (head == null)
return;
var prev = head;
var now = head.next;
while (prev != null && now != null) {
/* Change next link of previous node */
prev.next = now.next;
/* Free node */
now = null;
/* Update prev and now */
prev = prev.next;
if (prev != null)
now = prev.next;
}
}
/* Utility functions */
/* Inserts a new Node at front of the list. */
function push(new_data) {
/*
* 1 & 2: Allocate the Node & Put in the data
*/
var new_node = new Node(new_data);
/* 3. Make next of new Node as head */
new_node.next = head;
/* 4. Move the head to point to new Node */
head = new_node;
}
/* Function to print linked list */
function printList() {
var temp = head;
while (temp != null) {
document.write(temp.data + " ");
temp = temp.next;
}
document.write("<br/>");
}
/* Driver program to test above functions */
/* Constructed Linked List is
1->2->3->4->5->null */
push(5);
push(4);
push(3);
push(2);
push(1);
document.write(
"Linked List before calling deleteAlt() <br/>"
);
printList();
deleteAlt();
document.write(
"Linked List after calling deleteAlt()<br/> "
);
printList();
// This code contributed by gauravrajput1
</script>
Producción
List before calling deleteAlt() 1 2 3 4 5 List after calling deleteAlt() 1 3 5
Complejidad de tiempo: O(n)
donde n es el número de Nodes en la lista enlazada dada.
Espacio Auxiliar: O(1)
Como espacio adicional constante se utiliza.
Método 2 (recursivo)
El código recursivo utiliza el mismo enfoque que el método 1. El código recursivo es simple y corto pero hace que la función recursiva O(n) llame a una lista enlazada de tamaño n.
C++
/* deletes alternate nodes of a list starting with head */
void deleteAlt(Node *head)
{
if (head == NULL)
return;
Node *node = head->next;
if (node == NULL)
return;
/* Change the next link of head */
head->next = node->next;
/* free memory allocated for node */
free(node);
/* Recursively call for the new next of head */
deleteAlt(head->next);
}
// This code is contributed by rathbhupendra
C
/* deletes alternate nodes of a list starting with head */
void deleteAlt(struct Node *head)
{
if (head == NULL)
return;
struct Node *node = head->next;
if (node == NULL)
return;
/* Change the next link of head */
head->next = node->next;
/* free memory allocated for node */
free(node);
/* Recursively call for the new next of head */
deleteAlt(head->next);
}
Java
/* deletes alternate nodes of a list
starting with head */
static Node deleteAlt(Node head)
{
if (head == null)
return;
Node node = head.next;
if (node == null)
return;
/* Change the next link of head */
head.next = node.next;
/* Recursively call for the new next of head */
head.next = deleteAlt(head.next);
}
// This code is contributed by Arnab Kundu
Python3
# deletes alternate nodes of a list starting with head def deleteAlt(head): if (head == None): return node = head.next if (node == None): return # Change the next link of head head.next = node.next # free memory allocated for node #free(node) # Recursively call for the new next of head deleteAlt(head.next) # This code is contributed by Srathore
C#
/* deletes alternate nodes of a list
starting with head */
static Node deleteAlt(Node head)
{
if (head == null)
return;
Node node = head.next;
if (node == null)
return;
/* Change the next link of head */
head.next = node.next;
/* Recursively call for the new next of head */
head.next = deleteAlt(head.next);
}
// This code is contributed by Arnab Kundu
Javascript
<script>
/* deletes alternate nodes of a list
starting with head */
function deleteAlt(head)
{
if (head == null)
return;
var node = head.next;
if (node == null)
return;
/* Change the next link of head */
head.next = node.next; /* Recursively call for the new next of head */
head.next = deleteAlt(head.next);
}
// This code contributed by aashish1995
</script>
Complejidad de tiempo: O(n)
Espacio Auxiliar: O(1)
Como se trata de una función recursiva de cola, no se requiere una pila de llamadas de función, por lo que el espacio adicional utilizado es constante.
Escriba comentarios si encuentra que el código/algoritmo anterior es incorrecto, o encuentre mejores formas de resolver el mismo problema.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA