Programa de Python para eliminar la mitad de la lista vinculada

Dada una lista enlazada individualmente, elimine la mitad de la lista enlazada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la lista enlazada debe modificarse a 1->2->4->5

Si hay Nodes pares, entonces habría dos Nodes intermedios, debemos eliminar el segundo elemento intermedio. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5->6, entonces debe modificarse a 1->2->3->5->6.
Si la lista enlazada de entrada es NULL, entonces debería permanecer NULL.

Si la lista enlazada de entrada tiene 1 Node, entonces este Node debe eliminarse y debe devolverse un nuevo encabezado. 

Solución simple: la idea es primero contar el número de Nodes en una lista enlazada, luego eliminar el Node n/2 usando el proceso de eliminación simple. 

# Python3 program to delete middle
# of a linked list
   
# Link list Node 
class Node:    
    def __init__(self):        
        self.data = 0
        self.next = None
      
# Count of nodes
def countOfNodes(head):
    count = 0    
    while (head != None):
        head = head.next
        count += 1
      
    return count
  
# Deletes middle node and returns
# head of the modified list
def deleteMid(head):
  
    # Base cases
    if (head == None):
        return None
    if (head.next == None):
        del head
        return None
  
    copyHead = head
   
    # Find the count of nodes
    count = countOfNodes(head)
   
    # Find the middle node
    mid = count // 2
   
    # Delete the middle node
    while (mid > 1):
        mid -= 1
        head = head.next
   
    # Delete the middle node
    head.next = head.next.next
   
    return copyHead
  
# A utility function to print
# a given linked list
def printList(ptr):
    while (ptr != None):
        print(ptr.data, 
              end = '->')
        ptr = ptr.next
      
    print('NULL')
      
# Utility function to create 
# a new node.
def newNode(data):
    temp = Node()
    temp.data = data
    temp.next = None
    return temp
  
# Driver Code
if __name__=='__main__':
      
    # Start with the empty list
    head = newNode(1)
    head.next = newNode(2)
    head.next.next = newNode(3)
    head.next.next.next = newNode(4)
   
    print("Given Linked List")
    printList(head)
   
    head = deleteMid(head)
   
    print("Linked List after deletion of middle")
    printList(head)
  
# This code is contributed by rutvik_56

Producción:

Given Linked List
1->2->3->4->NULL
Linked List after deletion of middle
1->2->4->NULL

Análisis de Complejidad: 

• Complejidad temporal: O(n). 
  Se necesitan dos recorridos de la lista enlazada
• Espacio Auxiliar: O(1). 
  No se necesita espacio adicional.

Solución eficiente:  
Enfoque: La solución anterior requiere dos recorridos de la lista enlazada. El Node medio se puede eliminar usando un recorrido. La idea es usar dos punteros, slow_ptr y fast_ptr. Ambos punteros comienzan desde el encabezado de la lista. Cuando fast_ptr llega al final, slow_ptr llega al medio. Esta idea es la misma que la utilizada en el método 2 de esta publicación. Lo adicional en esta publicación es realizar un seguimiento del medio anterior para que se pueda eliminar el Node medio.

A continuación se muestra la implementación.

# Python3 program to delete the
# middle of a linked list
  
# Linked List Node
class Node:    
    def __init__(self, data):
        self.data = data
        self.next = None
  
# Create and handle list 
# operations
class LinkedList:    
    def __init__(self):
          
        # Head of the list
        self.head = None 
  
    # Add new node to the list end
    def addToList(self, data):        
        newNode = Node(data)
        if self.head is None:
            self.head = newNode
            return
              
        last = self.head
          
        while last.next:
            last = last.next
              
        last.next = newNode
  
    # Returns the list in string 
    # format
    def __str__(self):        
        linkedListStr = ""
        temp = self.head
          
        while temp:
            linkedListStr += str(temp.data) + "->"
            temp = temp.next
              
        return linkedListStr + "NULL"
  
    # Method deletes middle node
    def deleteMid(self):
  
        # Base cases
        if (self.head is None or 
            self.head.next is None):
            return
  
        # Initialize slow and fast pointers
        # to reach middle of linked list
        slow_Ptr = self.head
        fast_Ptr = self.head
  
        # Find the middle and previous of 
        # middle
        prev = None
  
        # To store previous of slow pointer
        while (fast_Ptr is not None and 
               fast_Ptr.next is not None):
            fast_Ptr = fast_Ptr.next.next
            prev = slow_Ptr
            slow_Ptr = slow_Ptr.next
  
        # Delete the middle node
        prev.next = slow_Ptr.next
  
# Driver code
linkedList = LinkedList()
  
linkedList.addToList(1)
linkedList.addToList(2)
linkedList.addToList(3)
linkedList.addToList(4)
  
print("Given Linked List")
print(linkedList)
  
linkedList.deleteMid()
  
print("Linked List after deletion of middle")
print(linkedList)
# This code is contributed by Debidutta Rath

Producción:

Given Linked List
1->2->3->4->NULL
Linked List after deletion of middle
1->2->4->NULL

Análisis de Complejidad: 

• Complejidad temporal: O(n). 
  Solo se necesita un recorrido de la lista enlazada
• Espacio Auxiliar: O(1). 
  Como no se necesita espacio adicional.

¡ Consulte el artículo completo sobre Eliminar el medio de la lista vinculada para obtener más detalles!