Programa de Python para encontrar el elemento medio de una lista enlazada dada

Dada una lista enlazada individualmente, busque el centro de la lista enlazada. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5, entonces la salida debería ser 3. 
Si hay Nodes pares, entonces habría dos Nodes intermedios, necesitamos imprimir el segundo intermedio. elemento. Por ejemplo, si la lista enlazada dada es 1->2->3->4->5->6, entonces la salida debería ser 4. 

Método 1: 
recorrer toda la lista enlazada y contar el no. de Nodes Ahora recorra la lista nuevamente hasta la cuenta/2 y devuelva el Node en la cuenta/2. 

Método 2: 
recorrer la lista enlazada usando dos punteros. Mueva un puntero por uno y los otros punteros por dos. Cuando el puntero rápido llegue al final, el puntero lento llegará a la mitad de la lista enlazada.

La siguiente imagen muestra cómo funciona la función printMiddle en el código:

# Python3 program to find middle of
# the linked list
# Node class
class Node:
   
    # Function to initialise the
    # node object
    def __init__(self, data):
    
        # Assign data
        self.data = data
 
        # Initialize next as null 
        self.next = None 
   
# Linked List class contains a
# Node object
class LinkedList:
   
    # Function to initialize head
    def __init__(self):
        self.head = None
 
    # Function to insert a new node at
    # the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node
 
    # Print the linked list
    def printList(self):
        node = self.head
        while node:
            print(str(node.data) +
                  "->", end = "")
            node = node.next
        print("NULL")
 
    # Function that returns middle.
    def printMiddle(self):
 
        # Initialize two pointers, one will go
        # one step a time (slow), another two
        # at a time (fast)
        slow = self.head
        fast = self.head
 
        # Iterate till fast's next is null (fast
        # reaches end)
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
         
        # Return the slow's data, which would be
        # the middle element.
        print("The middle element is ", slow.data)
 
# Driver code
if __name__=='__main__':
   
    # Start with the empty list
    llist = LinkedList()
   
    for i in range(5, 0, -1):
        llist.push(i)
        llist.printList()
        llist.printMiddle()
 
# This code is contributed by Kumar Shivam (kshivi99)

Producción:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

Método 3: 
Inicialice el elemento medio como cabeza e inicialice un contador como 0. Recorra la lista desde la cabeza, mientras recorre incremente el contador y cambie de mitad a mitad->siguiente siempre que el contador sea impar. Entonces, el medio se moverá solo la mitad de la longitud total de la lista. 
Gracias a Narendra Kangralkar por sugerir este método.  

# Python program to implement
# the above approach
 
# Node class
class Node:
    
    # Function to initialise the
    # node object
    def __init__(self, data):
 
        # Assign data 
        self.data = data 
 
        # Initialize next as null
        self.next = None 
    
# Linked List class contains a
# Node object
class LinkedList:
    
    # Function to initialize head
    def __init__(self):
        self.head = None
  
    # Function to insert a new node at
    # the beginning 
    def push(self, new_data): 
        new_node = Node(new_data) 
        new_node.next = self.head 
        self.head = new_node
  
    # Print the linked list
    def printList(self):
        node = self.head
        while node:
            print(str(node.data) +
                      "->", end = "")
            node = node.next
        print("NULL")
  
    # Function to get the middle of
    #  the linked list
    def printMiddle(self):
        count = 0
        mid = self.head
        heads = self.head
   
        while(heads != None):
       
        # Update mid, when 'count'
        # is odd number
            if count & 1:
                mid = mid.next
            count += 1
            heads = heads.next
             
        # If empty list is provided
        if mid != None:
            print("The middle element is ",
                   mid.data)
  
# Driver code
if __name__=='__main__':
    
    # Start with the empty list
    llist = LinkedList()
    
    for i in range(5, 0, -1):
        llist.push(i)
        llist.printList()
        llist.printMiddle()
  
 # This code is contributed by Manisha_Ediga

Producción:

5->NULL
The middle element is [5]

4->5->NULL
The middle element is [5]

3->4->5->NULL
The middle element is [4]

2->3->4->5->NULL
The middle element is [4]

1->2->3->4->5->NULL
The middle element is [3]

Complejidad de tiempo: O(n) donde n es el número de Nodes en la lista enlazada dada.
Espacio auxiliar: O(1), no se requiere espacio adicional, por lo que es una constante.

¡ Consulte el artículo completo sobre Encontrar el medio de una lista vinculada dada para obtener más detalles!