Dado que el encabezado de la lista enlazada representa un número entero positivo, la tarea es imprimir la lista enlazada actualizada después de restarle 1.
Ejemplos:
Entrada: LL = 1 -> 2 -> 3 -> 4
Salida: 1 -> 2 -> 3 -> 3Entrada: LL = 1 -> 2
Salida: 1 -> 1
Enfoque: El problema dado se puede resolver usando recursividad . Siga los pasos a continuación para resolver el problema:
- Defina una función , digamos subtractOneUtil(Node *head) que tome el encabezado de la lista vinculada como argumento y realice los siguientes pasos:
- Caso base: si el Node principal de la lista enlazada es NULL , devuelve -1 desde esa llamada recursiva.
- Llamada recursiva : llame recursivamente al siguiente Node de la lista enlazada y permita que se tome prestado el valor devuelto por esta llamada recursiva .
- Si el valor de préstamo es -1 y el valor del Node principal es 0 , actualice el valor del Node principal a 9 y devuelva -1 de la llamada recursiva actual.
- De lo contrario, disminuya el valor del Node principal en 1 y devuelva 0 desde la llamada recursiva actual.
- Reste 1 de la lista enlazada llamando a la función anterior como subtractOneUtil(head) .
- Si la lista vinculada actualizada tiene ceros iniciales , mueva el puntero principal.
- Después de completar los pasos anteriores, imprima la lista vinculada actualizada como la lista vinculada resultante.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program for the above approach
#include <bits/stdc++.h>
using namespace std;
// Linked list Node
class Node {
public:
int data;
Node* next;
};
// Function to create a new node with
// the given data
Node* newNode(int data)
{
// Create a new node
Node* new_node = new Node;
new_node->data = data;
new_node->next = NULL;
// Return the created node
return new_node;
}
// Recursive function to subtract 1
// from the linked list and update
// the node value accordingly
int subtractOneUtil(Node* head)
{
// Base Case
if (head == NULL)
return -1;
// Recursively call for the next
// node of the head
int borrow = subtractOneUtil(
head->next);
// If there is a borrow
if (borrow == -1) {
// If the head data is 0, then
// update it with 9 and return -1
if (head->data == 0) {
head->data = 9;
return -1;
}
// Otherwise, decrement head's
// data by 1 and return 0
else {
head->data = head->data - 1;
return 0;
}
}
// Otherwise, return 0
else {
return 0;
}
}
// Function to subtract 1 from the given
// Linked List representation of number
Node* subtractOne(Node* head)
{
// Recursively subtract 1 from
// the Linked List
subtractOneUtil(head);
// Increment the head pointer
// if there are any leading zeros
while (head and head->next
and head->data == 0) {
head = head->next;
}
return head;
}
// Function to print a linked list
void printList(Node* node)
{
// Iterate until node is NULL
while (node != NULL) {
cout << node->data;
node = node->next;
}
cout << endl;
}
// Driver Code
int main()
{
Node* head = newNode(1);
head->next = newNode(0);
head->next->next = newNode(0);
head->next->next->next = newNode(0);
cout << "List is ";
printList(head);
head = subtractOne(head);
cout << "Resultant list is ";
printList(head);
return 0;
}
Java
// Java program for the above approach
import java.util.*;
class GFG{
// Linked list Node
static class Node
{
int data;
Node next;
};
// Function to create a new node with
// the given data
static Node newNode(int data)
{
// Create a new node
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
// Return the created node
return new_node;
}
// Recursive function to subtract 1
// from the linked list and update
// the node value accordingly
static int subtractOneUtil(Node head)
{
// Base Case
if (head == null)
return -1;
// Recursively call for the next
// node of the head
int borrow = subtractOneUtil(
head.next);
// If there is a borrow
if (borrow == -1)
{
// If the head data is 0, then
// update it with 9 and return -1
if (head.data == 0)
{
head.data = 9;
return -1;
}
// Otherwise, decrement head's
// data by 1 and return 0
else
{
head.data = head.data - 1;
return 0;
}
}
// Otherwise, return 0
else
{
return 0;
}
}
// Function to subtract 1 from the given
// Linked List representation of number
static Node subtractOne(Node head)
{
// Recursively subtract 1 from
// the Linked List
subtractOneUtil(head);
// Increment the head pointer
// if there are any leading zeros
while (head != null && head.next != null &&
head.data == 0)
{
head = head.next;
}
return head;
}
// Function to print a linked list
static void printList(Node node)
{
// Iterate until node is null
while (node != null)
{
System.out.print(node.data);
node = node.next;
}
System.out.println();
}
// Driver Code
public static void main(String[] args)
{
Node head = newNode(1);
head.next = newNode(0);
head.next.next = newNode(0);
head.next.next.next = newNode(0);
System.out.print("List is ");
printList(head);
head = subtractOne(head);
System.out.print("Resultant list is ");
printList(head);
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program for the above approach
# Linked list Node
class Node:
def __init__(self, d):
self.data = d
self.next = None
# Recursive function to subtract 1
# from the linked list and update
# the node value accordingly
def subtractOneUtil(head):
# Base Case
if (head == None):
return -1
# Recursively call for the next
# node of the head
borrow = subtractOneUtil(head.next)
# If there is a borrow
if (borrow == -1):
# If the head data is 0, then
# update it with 9 and return -1
if (head.data == 0):
head.data = 9
return -1
# Otherwise, decrement head's
# data by 1 and return 0
else:
head.data = head.data - 1
return 0
# Otherwise, return 0
else:
return 0
# Function to subtract 1 from the given
# Linked List representation of number
def subtractOne(head):
# Recursively subtract 1 from
# the Linked List
subtractOneUtil(head)
# Increment the head pointer
# if there are any leading zeros
while (head and head.next and
head.data == 0):
head = head.next
return head
# Function to pra linked list
def printList(node):
# Iterate until node is None
while (node != None):
print(node.data, end = "")
node = node.next
print()
# Driver Code
if __name__ == '__main__':
head = Node(1)
head.next = Node(0)
head.next.next = Node(0)
head.next.next.next = Node(0)
print("List is ", end = "")
printList(head)
head = subtractOne(head)
print("Resultant list is ", end = "")
printList(head)
# This code is contributed by mohit kumar 29
C#
// C# program for the above approach
using System;
class GFG{
// Linked list Node
class Node
{
public int data;
public Node next;
};
// Function to create a new node with
// the given data
static Node newNode(int data)
{
// Create a new node
Node new_node = new Node();
new_node.data = data;
new_node.next = null;
// Return the created node
return new_node;
}
// Recursive function to subtract 1
// from the linked list and update
// the node value accordingly
static int subtractOneUtil(Node head)
{
// Base Case
if (head == null)
return -1;
// Recursively call for the next
// node of the head
int borrow = subtractOneUtil(
head.next);
// If there is a borrow
if (borrow == -1)
{
// If the head data is 0, then
// update it with 9 and return -1
if (head.data == 0)
{
head.data = 9;
return -1;
}
// Otherwise, decrement head's
// data by 1 and return 0
else
{
head.data = head.data - 1;
return 0;
}
}
// Otherwise, return 0
else
{
return 0;
}
}
// Function to subtract 1 from the given
// Linked List representation of number
static Node subtractOne(Node head)
{
// Recursively subtract 1 from
// the Linked List
subtractOneUtil(head);
// Increment the head pointer
// if there are any leading zeros
while (head != null && head.next != null &&
head.data == 0)
{
head = head.next;
}
return head;
}
// Function to print a linked list
static void printList(Node node)
{
// Iterate until node is null
while (node != null)
{
Console.Write(node.data);
node = node.next;
}
Console.WriteLine();
}
// Driver Code
public static void Main()
{
Node head = newNode(1);
head.next = newNode(0);
head.next.next = newNode(0);
head.next.next.next = newNode(0);
Console.Write("List is ");
printList(head);
head = subtractOne(head);
Console.Write("Resultant list is ");
printList(head);
}
}
// This code is contributed by SURENDRA_GANGWAR
Javascript
<script>
// JavaScript program for the above approach
// Linked list Node
class Node
{
constructor()
{
this.next = null;
}
}
// Function to create a new node with
// the given data
function newNode(data)
{
// Create a new node
let new_node = new Node();
new_node.data = data;
new_node.next = null;
// Return the created node
return new_node;
}
// Recursive function to subtract 1
// from the linked list and update
// the node value accordingly
function subtractOneUtil(head)
{
// Base Case
if (head == null)
return -1;
// Recursively call for the next
// node of the head
let borrow = subtractOneUtil(head.next);
// If there is a borrow
if (borrow == -1)
{
// If the head data is 0, then
// update it with 9 and return -1
if (head.data == 0)
{
head.data = 9;
return -1;
}
// Otherwise, decrement head's
// data by 1 and return 0
else
{
head.data = head.data - 1;
return 0;
}
}
// Otherwise, return 0
else
{
return 0;
}
}
// Function to subtract 1 from the given
// Linked List representation of number
function subtractOne(head)
{
// Recursively subtract 1 from
// the Linked List
subtractOneUtil(head);
// Increment the head pointer
// if there are any leading zeros
while (head != null && head.next != null &&
head.data == 0)
{
head = head.next;
}
return head;
}
// Function to print a linked list
function printList(node)
{
// Iterate until node is null
while (node != null)
{
document.write(node.data);
node = node.next;
}
document.write("<br>");
}
// Driver Code
let head = newNode(1);
head.next = newNode(0);
head.next.next = newNode(0);
head.next.next.next = newNode(0);
document.write("List is ");
printList(head);
head = subtractOne(head);
document.write("Resultant list is ");
printList(head);
// This code is contributed by Dharanendra L V.
</script>
Producción:
List is 1000 Resultant list is 999
Complejidad de tiempo: O(N), N es la longitud de la lista enlazada dada .
Espacio Auxiliar: O(1)
Publicación traducida automáticamente
Artículo escrito por kartikey134 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA