Programa de Python para insertar un Node en medio de la lista enlazada

Dada una lista enlazada que contiene n Nodes. El problema es insertar un nuevo Node con datos x en el medio de la lista. Si n es par, entonces inserte el nuevo Node después del (n/2) enésimo Node, de lo contrario, inserte el nuevo Node después del (n+1)/2 enésimo Node.

Ejemplos: 

Input : list: 1->2->4->5
        x = 3
Output : 1->2->3->4->5

Input : list: 5->10->4->32->16
        x = 41
Output : 5->10->4->41->32->16

Método 1 (Usando la longitud de la lista enlazada): 
Encuentre la cantidad de Nodes o la longitud del enlace usando un recorrido. Que sea len . Calcule c = (len/2), si len es par, de lo contrario, c = (len+1)/2, si len es impar. Atraviese de nuevo los primeros c Nodes e inserte el nuevo Node después del c -ésimo Node.  

# Python3 implementation to insert node
# at the middle of a linked list
 
# Node class
class Node:
 
    # constructor to create a new node
    def __init__(self, data):
        self.data = data
        self.next = None
 
# function to insert node at the
# middle of linked list given the head
def insertAtMid(head, x):
 
    if(head == None): #if the list is empty
        head = Node(x)
    else:
         
        # create a new node for the value
        # to be inserted
        newNode = Node(x)
 
        ptr = head
        length = 0
         
        # calculate the length of the linked
        # list
        while(ptr != None):
            ptr = ptr.next
            length += 1
 
        # 'count' the number of node after which
        # the new node has to be inserted
        if(length % 2 == 0):
            count = length / 2
        else:
            (length + 1) / 2
 
        ptr = head
 
        # move ptr to the node after which
        # the new node has to inserted
        while(count > 1):
            count -= 1
            ptr = ptr.next
 
        # insert the 'newNode' and adjust
        # links accordingly
        newNode.next = ptr.next
        ptr.next = newNode
 
# function to display the linked list
def display(head):
    temp = head
    while(temp != None):
        print(str(temp.data), end = " ")
        temp = temp.next
 
# Driver Code
 
# Creating the linked list 1.2.4.5
head = Node(1)
head.next = Node(2)
head.next.next = Node(4)
head.next.next.next = Node(5)
 
print("Linked list before insertion: ", end = "")
display(head)
 
# inserting 3 in the middle of the linked list.
x = 3
insertAtMid(head, x)
 
print("
Linked list after insertion: " , end = "")
display(head)
 
# This code is contributed by Pranav Devarakonda

Producción: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Complejidad de tiempo: O(n)

Complejidad del espacio : O(n) donde n es el número de Nodes en una lista enlazada

Método 2 (usando dos punteros): 
basado en el algoritmo de Turtle y liebre que usa dos punteros, uno conocido como lento y el otro conocido como rápido . Este algoritmo ayuda a encontrar el Node medio de la lista enlazada. Se explica en el procedimiento de división frontal y negro de esta publicación. Ahora, puede insertar el nuevo Node después del Node medio obtenido del proceso anterior. Este enfoque requiere solo un único recorrido de la lista. 

# Python implementation to insert node
# at the middle of the linked list
 
# Node Class
class Node :
    def __init__(self, d):
        self.data = d
        self.next = None
         
class LinkedList:
 
    # function to insert node at the
    # middle of the linked list
    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
         
    def insertAtMid(self, x):
         
        # if list is empty
        if (self.head == None):
            self.head = Node(x)
 
        else:
             
            # get a new node
            newNode = Node(x)
 
            # assign values to the slow
            # and fast pointers
            slow = self.head
            fast = self.head.next
 
            while (fast != None and
                   fast.next != None):
                 
                # move slow pointer to next node
                slow = slow.next
 
                # move fast pointer two nodes
                # at a time
                fast = fast.next.next
 
            # insert the 'newNode' and
            # adjust the required links
            newNode.next = slow.next
            slow.next = newNode
 
    # function to display the linked list
    def display(self):
        temp = self.head
        while (temp != None):
            print(temp.data, end = " "),
            temp = temp.next
 
# Driver Code
 
# Creating the list 1.2.4.5
ll = LinkedList()
ll.push(5)
ll.push(4)
ll.push(2)
ll.push(1)
print("Linked list before insertion: "),
ll.display()
 
x = 3
ll.insertAtMid(x)
 
print("
Linked list after insertion: "),
ll.display()
 
# This code is contributed by prerna saini

Producción: 

Linked list before insertion: 1 2 4 5
Linked list after insertion: 1 2 3 4 5

Complejidad de tiempo: O(n)

Complejidad del espacio : O(n) donde n es el tamaño de la lista enlazada

Consulte el artículo completo sobre Insertar Node en el medio de la lista vinculada para obtener más detalles.