Programa de Python para agregar 1 a un número representado como lista vinculada

El número se representa en la lista enlazada de modo que cada dígito corresponde a un Node en la lista enlazada. Súmale 1. Por ejemplo, 1999 se representa como (1-> 9-> 9 -> 9) y agregarle 1 debería cambiarlo a (2->0->0->0) 

A continuación se muestran los pasos: 

1. Lista enlazada inversa dada. Por ejemplo, 1-> 9-> 9 -> 9 se convierte en 9-> 9 -> 9 ->1.
2. Comience a recorrer la lista enlazada desde el Node más a la izquierda y agréguele 1. Si hay un acarreo, pasa al siguiente Node. Continúe moviéndose al siguiente Node mientras haya un acarreo.
3. Invierta la lista enlazada modificada y devuelva el encabezado.

A continuación se muestra la implementación de los pasos anteriores. 

# Python3 program to add 1 to 
# a linked list
import sys
import math
  
# Linked list node
class Node:
    def __init__(self, data):
        self.data = data
        self.next = None
  
# Function to create a new node 
# with given data 
def newNode(data):
    return Node(data)
  
# Function to reverse the 
# linked list
def reverseList(head):
    if not head:
        return
    curNode = head
    prevNode = head
    nextNode = head.next
    curNode.next = None
  
    while(nextNode):
        curNode = nextNode
        nextNode = nextNode.next
        curNode.next = prevNode
        prevNode = curNode
  
    return curNode
  
# Adds one to a linked lists and 
# return the head node of 
# resultant list
def addOne(head):
  
    # Reverse linked list and add 
    # one to head
    head = reverseList(head)
    k = head
    carry = 0
    prev = None
    head.data += 1
  
    # update carry for next calculation
    while(head != None) and (head.data > 9 or carry > 0):
        prev = head
        head.data += carry
        carry = head.data // 10
        head.data = head.data % 10
        head = head.next
  
    if carry > 0:
        prev.next = Node(carry)
    # Reverse the modified list
    return reverseList(k)
  
# A utility function to print 
# a linked list
def printList(head):
    if not head:
        return
  
    while(head):
        print("{}".format(head.data), end="")
        head = head.next
  
# Driver code
if __name__ == '__main__':
    head = newNode(1)
    head.next = newNode(9)
    head.next.next = newNode(9)
    head.next.next.next = newNode(9)
  
    print("List is: ", 
           end = "")
    printList(head)
  
    head = addOne(head)
  
    print("Resultant list is: ", 
           end = "")
    printList(head)
# This code is contributed by Rohit

Producción:

List is 1999
Resultant list is 2000

Implementación recursiva: 
podemos llegar recursivamente al último Node y reenviar el transporte a los Nodes anteriores. La solución recursiva no requiere la inversión de la lista enlazada. También podemos usar una pila en lugar de recursividad para contener Nodes temporalmente.

A continuación se muestra la implementación de la solución recursiva.

# Recursive Python program to add 1 to 
# a linked list
  
# Node class 
class Node: 
  
    # Constructor to initialize 
    # the node object 
    def __init__(self, data): 
        self.data = data 
        self.next = None
  
# Function to create a new node 
# with given data 
def newNode(data):
  
    new_node = Node(0)
    new_node.data = data
    new_node.next = None
    return new_node
  
# Recursively add 1 from end to beginning 
# and returns carry after all nodes are 
# processed.
def addWithCarry(head):
  
    # If linked list is empty, then
    # return carry
    if (head == None):
        return 1
  
    # Add carry returned be next node 
    # call
    res = head.data + addWithCarry(head.next)
  
    # Update data and return new carry
    head.data = int((res) % 10)
    return int((res) / 10)
  
# This function mainly uses 
# addWithCarry().
def addOne(head):
  
    # Add 1 to linked list from end 
    # to beginning
    carry = addWithCarry(head)
  
    # If there is carry after processing 
    # all nodes, then we need to add a 
    # new node to linked list
    if (carry != 0):
      
        newNode = Node(0)
        newNode.data = carry
        newNode.next = head
  
        # New node becomes head now
        return newNode 
      
    return head
  
# A utility function to print a 
# linked list
def printList(node):
  
    while (node != None):    
        print(node.data,
              end = "")
        node = node.next
      
    print("")
  
# Driver code
head = newNode(1)
head.next = newNode(9)
head.next.next = newNode(9)
head.next.next.next = newNode(9)
  
print("List is ")
printList(head)
  
head = addOne(head)
  
print("Resultant list is ")
printList(head)
# This code is contributed by Arnab Kundu

Producción:

List is 1999
Resultant list is 2000

¡ Consulte el artículo completo sobre Agregar 1 a un número representado como una lista vinculada para obtener más detalles!