Subtract 1 from a number represented as Linked List
Given the head of the linked list representing a positive integer, the task is to print the updated linked list after subtracting 1 from it.
Examples:
Input: LL = 1 -> 2 -> 3 -> 4
Output: 1 -> 2 -> 3 -> 3Input: LL = 1 -> 2
Output: 1 -> 1
Approach: The given problem can be solved by using recursion. Follow the steps below to solve the problem:
- Define a function, say subtractOneUtil(Node *head) that takes the head of the linked list as the arguments and perform the following steps:
- Base Case: If the head node of the Linked List is NULL, then return -1 from that recursive call.
- Recursive Call: Recursively call for the next node of the linked list and let the value returned by this recursive call be borrow.
- If the value of borrow is -1 and the value of the head node is 0, then update the value of the head node to 9 and return -1 from the current recursive call.
- Otherwise, decrement the value of the head node by 1 and return 0 from the current recursive call.
- Subtract 1 from the Linked List by calling the above function as subtractOneUtil(head).
- If the update linked list has leading 0s, then move the head pointer.
- After completing the above steps, print the updated linked list as the resultant linked list.
Below is the implementation of the above approach:
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 print a 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> |
Output
List is 1000 Resultant list is 999
Time Complexity: O(N), N is the length of the given linked list.
Auxiliary Space: O(1)
New Approach by reverse the linked list :
- Subtract 1 from the first node (i.e., the ones place), and then handle the carry if require.
- .Then, reverse the linked list back to its original form and return the updated linked list.
Below is the implementation of the above approach:
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; } // Function to reverse a linked list Node* reverseList(Node* head) { Node *prev = NULL, *curr = head, *next; while (curr != NULL) { next = curr->next; curr->next = prev; prev = curr; curr = next; } return prev; } // Function to subtract 1 from the given // Linked List representation of number Node* subtractOne(Node* head) { // Reverse the linked list head = reverseList(head); // Subtract 1 from the first node head->data -= 1; // Handle the carry if required Node* curr = head; while (curr->data < 0) { curr->data += 10; if (curr->next == NULL) { curr->next = newNode(0); } curr->next->data -= 1; curr = curr->next; } // Reverse the linked list back to // its original form head = reverseList(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; } //This code is contributed by chinmaya121221 |
Java
public class Main { // 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; } // Function to reverse a linked list static Node reverseList(Node head) { Node prev = null , curr = head, next; while (curr != null ) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } // Function to subtract 1 from the given // Linked List representation of number static Node subtractOne(Node head) { // Reverse the linked list head = reverseList(head); // Subtract 1 from the first node head.data -= 1 ; // Handle the carry if required Node curr = head; while (curr.data < 0 ) { curr.data += 10 ; if (curr.next == null ) { curr.next = newNode( 0 ); } curr.next.data -= 1 ; curr = curr.next; } // Reverse the linked list back to // its original form head = reverseList(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(); } 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); } } |
Python3
# Linked list Node class Node: def __init__( self , data): self .data = data self . next = None # Function to create a new node with the given data def newNode(data): # Create a new node new_node = Node(data) # Return the created node return new_node # Function to reverse a linked list def reverseList(head): prev = None curr = head next = None while curr ! = None : next = curr. next curr. next = prev prev = curr curr = next return prev # Function to subtract 1 from the given # Linked List representation of number def subtractOne(head): # Reverse the linked list head = reverseList(head) # Subtract 1 from the first node head.data - = 1 # Handle the carry if required curr = head while curr.data < 0 : curr.data + = 10 if curr. next = = None : curr. next = newNode( 0 ) curr. next .data - = 1 curr = curr. next # Reverse the linked list back to its original form head = reverseList(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 def printList(node): # Iterate until node is NULL while node ! = None : print (node.data, end = "") node = node. next print () # Driver Code head = newNode( 1 ) head. next = newNode( 0 ) head. next . next = newNode( 0 ) head. next . next . next = newNode( 0 ) print ( "List is " ) printList(head) head = subtractOne(head) print ( "Resultant list is " ) printList(head) |
C#
// C# program for the above approach using System; // Linked list Node class Node { public int data; public Node next; }; // Main class class MainClass { // 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; } // Function to reverse a linked list static Node reverseList(Node head) { Node prev = null , curr = head, next; while (curr != null ) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } // Function to subtract 1 from the given // Linked List representation of number static Node subtractOne(Node head) { // Reverse the linked list head = reverseList(head); // Subtract 1 from the first node head.data -= 1; // Handle the carry if required Node curr = head; while (curr.data < 0) { curr.data += 10; if (curr.next == null ) { curr.next = newNode(0); } curr.next.data -= 1; curr = curr.next; } // Reverse the linked list back to // its original form head = reverseList(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 rutikbhosale |
Javascript
// Linked list Node class Node { constructor(data) { this .data = data; 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(data); // Return the created node return new_node; } // Function to reverse a linked list function reverseList(head) { let prev = null , curr = head, next; while (curr != null ) { next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; } // Function to subtract 1 from the given // Linked List representation of number function subtractOne(head) { // Reverse the linked list head = reverseList(head); // Subtract 1 from the first node head.data -= 1; // Handle the carry if required let curr = head; while (curr.data < 0) { curr.data += 10; if (curr.next == null ) { curr.next = newNode(0); } curr.next.data -= 1; curr = curr.next; } // Reverse the linked list back to its original form head = reverseList(head); // Increment the head pointer if there are any leading zeros while (head && head.next && 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 ) { process.stdout.write(node.data + "" ); node = node.next; } console.log(); } // Driver Code let head = newNode(1); head.next = newNode(0); head.next.next = newNode(0); head.next.next.next = newNode(0); console.log( "List is " ); printList(head); head = subtractOne(head); console.log( "Resultant list is " ); printList(head); |
Output
List is 1000 Resultant list is 999
Time Complexity: O(n), where n is the length of the linked list.
Space Complexity: O(n), where n is the length of the linked list.
Another approach using Stack:
C++
#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; } // Function to subtract 1 from the given // Linked List representation of number using stack Node* subtractOne(Node* head) { stack< int > s; // Traverse the linked list and push values onto the stack Node* curr = head; while (curr != NULL) { s.push(curr->data); curr = curr->next; } int borrow = 1; Node* new_head = NULL; // Pop elements from the stack and subtract borrow while (!s.empty()) { int val = s.top() - borrow; borrow = 0; if (val < 0) { val += 10; borrow = 1; } s.pop(); Node* new_node = newNode(val); new_node->next = new_head; new_head = new_node; } // Remove leading zeros while (new_head != NULL && new_head->data == 0) { Node* temp = new_head; new_head = new_head->next; delete temp; } return new_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; } // Nikunj Sonigara // 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
import java.util.Stack; // Linked list Node class Node { int data; Node next; Node( int data) { this .data = data; this .next = null ; } } public class Main { // Function to subtract 1 from the given // Linked List representation of number using stack static Node subtractOne(Node head) { Stack<Integer> s = new Stack<>(); // Traverse the linked list and push values onto the // stack Node curr = head; while (curr != null ) { s.push(curr.data); curr = curr.next; } int borrow = 1 ; Node new_head = null ; // Pop elements from the stack and subtract borrow while (!s.empty()) { int val = s.pop() - borrow; borrow = 0 ; if (val < 0 ) { val += 10 ; borrow = 1 ; } Node new_node = new Node(val); new_node.next = new_head; new_head = new_node; } // Remove leading zeros while (new_head != null && new_head.data == 0 ) { Node temp = new_head; new_head = new_head.next; temp = null ; } return new_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 = new Node( 1 ); head.next = new Node( 0 ); head.next.next = new Node( 0 ); head.next.next.next = new Node( 0 ); System.out.print( "List is " ); printList(head); head = subtractOne(head); System.out.print( "Resultant list is " ); printList(head); } } |
Python
# Linked list Node class Node: def __init__( self , data): self .data = data self . next = None # Function to create a new node with the given data def new_node(data): # Create a new node new_node = Node(data) # Return the created node return new_node # Function to subtract 1 from the given Linked List representation of number using stack def subtract_one(head): stack = [] # Traverse the linked list and push values onto the stack curr = head while curr is not None : stack.append(curr.data) curr = curr. next borrow = 1 new_head = None # Pop elements from the stack and subtract borrow while stack: val = stack.pop() - borrow borrow = 0 if val < 0 : val + = 10 borrow = 1 new_node = Node(val) new_node. next = new_head new_head = new_node # Remove leading zeros while new_head is not None and new_head.data = = 0 : temp = new_head new_head = new_head. next del temp return new_head # Function to print a linked list def print_list(node): # Iterate until node is None while node is not None : print node.data, # Adding a comma to suppress the newline character node = node. next print # Print a newline after the loop # Driver Code if __name__ = = "__main__" : head = new_node( 1 ) head. next = new_node( 0 ) head. next . next = new_node( 0 ) head. next . next . next = new_node( 0 ) print "List is " , print_list(head) head = subtract_one(head) print "Resultant list is " , print_list(head) # Contributed by sinudp5vi |
C#
using System; using System.Collections.Generic; // Linked list Node class Node { public int data; public Node next; } class GFG { // 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; } // Function to subtract 1 from the given // Linked List representation of number using stack static Node SubtractOne(Node head) { Stack< int > stack = new Stack< int >(); // Traverse the linked list and push values onto the // stack Node curr = head; while (curr != null ) { stack.Push(curr.data); curr = curr.next; } int borrow = 1; Node new_head = null ; // Pop elements from the stack and subtract borrow while (stack.Count > 0) { int val = stack.Pop() - borrow; borrow = 0; if (val < 0) { val += 10; borrow = 1; } Node new_node = NewNode(val); new_node.next = new_head; new_head = new_node; } // Remove leading zeros while (new_head != null && new_head.data == 0) { new_head = new_head.next; } return new_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 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); } } |
Javascript
// Linked list Node class Node { constructor(data) { this .data = data; this .next = null ; } } // Function to create a new node with the given data function new_node(data) { // Create a new node const new_node = new Node(data); // Return the created node return new_node; } // Function to subtract 1 from the given Linked List representation of number using stack function subtract_one(head) { const stack = []; // Traverse the linked list and push values onto the stack let curr = head; while (curr !== null ) { stack.push(curr.data); curr = curr.next; } let borrow = 1; let new_head = null ; // Pop elements from the stack and subtract borrow while (stack.length > 0) { let val = stack.pop() - borrow; borrow = 0; if (val < 0) { val += 10; borrow = 1; } const new_node = new Node(val); new_node.next = new_head; new_head = new_node; } // Remove leading zeros while (new_head !== null && new_head.data === 0) { const temp = new_head; new_head = new_head.next; // Delete temp (Not required in JavaScript as memory management is automatic) } return new_head; } // Function to print a linked list function print_list(node) { // Iterate until node is null while (node !== null ) { console.log(node.data); node = node.next; } } // Driver Code const head = new_node(1); head.next = new_node(0); head.next.next = new_node(0); head.next.next.next = new_node(0); console.log( "List is:" ); print_list(head); const newHead = subtract_one(head); console.log( "Resultant list is:" ); print_list(newHead); |
Output
List is 1000 Resultant list is 999
Time Complexity: O(n)
Space Complexity: O(n)