Programa de Python para insertar un Node después del enésimo Node desde el final

Inserte un Node x después del enésimo Node desde el final en la lista enlazada simple dada. Se garantiza que la lista contiene el Node n desde el final. También 1 <= n.

Ejemplos: 

Input : list: 1->3->4->5
        n = 4, x = 2
Output : 1->2->3->4->5
4th node from the end is 1 and
insertion has been done after this node.

Input : list: 10->8->3->12->5->18
        n = 2, x = 11
Output : 10->8->3->12->5->11->18

Método 1 (usando la longitud de la lista):
Encuentre la longitud de la lista enlazada, es decir, el número de Nodes en la lista. Que sea len . Ahora recorra la lista desde el primer Node hasta el (largo-n+1) Node desde el principio e inserte el nuevo Node después de este Node. Este método requiere dos recorridos de la lista. 

# Python implementation to insert a node after 
# the n-th node from the end 
  
# Linked List node 
class Node: 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# function to get a new node 
def getNode(data) :
  
    # allocate memory for the node 
    newNode = Node(0) 
  
    # put in the data 
    newNode.data = data 
    newNode.next = None
    return newNode 
  
# function to insert a node after the 
# nth node from the end 
def insertAfterNthNode(head, n, x) :
  
    # if list is empty 
    if (head == None) :
        return
  
    # get a new node for the value 'x' 
    newNode = getNode(x) 
    ptr = head 
    len = 0
    i = 0
  
    # find length of the list, i.e, the 
    # number of nodes in the list 
    while (ptr != None) :
      
        len = len + 1
        ptr = ptr.next
      
    # traverse up to the nth node from the end 
    ptr = head 
    i = 1
    while ( i <= (len - n) ) :
        ptr = ptr.next
        i = i + 1
  
    # insert the 'newNode' by making the 
    # necessary adjustment in the links 
    newNode.next = ptr.next
    ptr.next = newNode 
  
# function to print the list 
def printList( head) :
  
    while (head != None):
      
        print(head.data ,end = " ") 
        head = head.next
      
# Driver code 
  
# Creating list 1->3->4->5 
head = getNode(1) 
head.next = getNode(3) 
head.next.next = getNode(4) 
head.next.next.next = getNode(5) 
  
n = 4
x = 2
  
print("Original Linked List: ") 
printList(head) 
  
insertAfterNthNode(head, n, x) 
print()
print("Linked List After Insertion: ") 
printList(head) 
  
# This code is contributed by Arnab Kundu

Producción:

Original Linked List: 1 3 4 5
Linked List After Insertion: 1 2 3 4 5

Complejidad temporal: O(n), donde n es el número de Nodes de la lista.

Método 2 (recorrido simple):
este método utiliza dos punteros, uno es slow_ptr y el otro es fast_ptr . Primero mueva fast_ptr hasta el Node n desde el principio. Haga que slow_ptr apunte al primer Node de la lista. Ahora, mueva simultáneamente ambos punteros hasta que fast_ptr apunte al último Node. En este punto , slow_ptr apuntará al Node n desde el final. Inserte el nuevo Node después de este Node. Este método requiere un solo recorrido de la lista.

# Python3 implementation to insert a
# node after the nth node from the end
   
# Structure of a node
class Node:
      
    def __init__(self, data):
          
        self.data = data
        self.next = None
      
# Function to get a new node
def getNode(data):
      
    # Allocate memory for the node
    newNode = Node(data)
    return newNode
  
# Function to insert a node after the
# nth node from the end
def insertAfterNthNode(head, n, x):
  
    # If list is empty
    if (head == None):
        return
   
    # Get a new node for the value 'x'
    newNode = getNode(x)
   
    # Initializing the slow and fast pointers
    slow_ptr = head
    fast_ptr = head
   
    # Move 'fast_ptr' to point to the nth
    # node from the beginning
    for i in range(1, n):
        fast_ptr = fast_ptr.next
   
    # Iterate until 'fast_ptr' points to the
    # last node
    while (fast_ptr.next != None):
   
        # Move both the pointers to the
        # respective next nodes
        slow_ptr = slow_ptr.next
        fast_ptr = fast_ptr.next
  
    # Insert the 'newNode' by making the
    # necessary adjustment in the links
    newNode.next = slow_ptr.next
    slow_ptr.next = newNode
  
# Function to print the list
def printList(head):
  
    while (head != None):
        print(head.data, end = ' ')
        head = head.next
      
# Driver code
if __name__=='__main__':
      
    # Creating list 1.3.4.5
    head = getNode(1)
    head.next = getNode(3)
    head.next.next = getNode(4)
    head.next.next.next = getNode(5)
   
    n = 4
    x = 2
   
    print("Original Linked List: ", end = '')
    printList(head)
   
    insertAfterNthNode(head, n, x)
   
    print("
Linked List After Insertion: ", end = '')
    printList(head)
   
# This code is contributed by rutvik_56

Producción: 

Original Linked List: 1 3 4 5
Linked List After Insertion: 1 2 3 4 5

Complejidad temporal: O(n), donde n es el número de Nodes de la lista.

Consulte el artículo completo sobre Insertar un Node después del Node n desde el final para obtener más detalles.