Programa de Python para eliminar Nodes alternativos de una lista vinculada

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 de la anterior del Node que se eliminará. Primero, cambie el siguiente enlace del Node anterior y muévase iterativamente al siguiente Node.

# 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 po 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 
    # 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("List after calling deleteAlt() ") 
    printList(head) 
# This code is contributed by Srathore

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.

Método 2 (recursivo): 
el código recursivo utiliza el mismo enfoque que el método 1. El código recursivo es simple y breve, pero hace que la función recursiva O(n) llame a una lista vinculada de tamaño n.

# 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

Complejidad de tiempo: O(n)

Consulte el artículo completo sobre Eliminar Nodes alternativos de una lista vinculada para obtener más detalles.