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 Nodeclass Node {public: int data; Node* next;};// Function to create a new node with// the given dataNode* 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 accordinglyint 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 numberNode* 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 listvoid printList(Node* node){ // Iterate until node is NULL while (node != NULL) { cout << node->data; node = node->next; } cout << endl;}// Driver Codeint 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 approachimport java.util.*;class GFG{// Linked list Nodestatic class Node { int data; Node next;};// Function to create a new node with// the given datastatic 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 accordinglystatic 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 numberstatic 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 liststatic void printList(Node node){ // Iterate until node is null while (node != null) { System.out.print(node.data); node = node.next; } System.out.println();}// Driver Codepublic 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 Nodeclass 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 accordinglydef 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 numberdef 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 listdef printList(node): # Iterate until node is None while (node != None): print(node.data, end = "") node = node.next print()# Driver Codeif __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 approachusing System;class GFG{// Linked list Nodeclass Node { public int data; public Node next;};// Function to create a new node with// the given datastatic 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 accordinglystatic 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 numberstatic 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 liststatic void printList(Node node){ // Iterate until node is null while (node != null) { Console.Write(node.data); node = node.next; } Console.WriteLine();}// Driver Codepublic 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 Nodeclass Node { constructor() { this.next = null; }}// Function to create a new node with// the given datafunction 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 accordinglyfunction 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 numberfunction 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 listfunction printList(node){ // Iterate until node is null while (node != null) { document.write(node.data); node = node.next; } document.write("<br>");}// Driver Codelet 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 Nodeclass Node {public: int data; Node* next;};// Function to create a new node with// the given dataNode* 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 listNode* 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 numberNode* 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 listvoid printList(Node* node){ // Iterate until node is NULL while (node != NULL) { cout << node->data; node = node->next; } cout << endl;}// Driver Codeint 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 Nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to create a new node with the given datadef newNode(data): # Create a new node new_node = Node(data) # Return the created node return new_node# Function to reverse a linked listdef 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 numberdef 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 listdef printList(node): # Iterate until node is NULL while node != None: print(node.data, end="") node = node.next print()# Driver Codehead = 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 approachusing System;// Linked list Nodeclass Node { public int data; public Node next;};// Main classclass 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 Nodeclass Node { constructor(data) { this.data = data; this.next = null; }}// Function to create a new node with the given datafunction newNode(data) { // Create a new node let new_node = new Node(data); // Return the created node return new_node;}// Function to reverse a linked listfunction 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 numberfunction 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 listfunction printList(node) { // Iterate until node is NULL while (node != null) { process.stdout.write(node.data + ""); node = node.next; } console.log();}// Driver Codelet 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 Nodeclass Node {public: int data; Node* next;};// Function to create a new node with// the given dataNode* 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 stackNode* 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 listvoid printList(Node* node){ // Iterate until node is NULL while (node != NULL) { cout << node->data; node = node->next; } cout << endl;}// Nikunj Sonigara// Driver Codeint 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 Nodeclass 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 Nodeclass Node: def __init__(self, data): self.data = data self.next = None# Function to create a new node with the given datadef 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 stackdef 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 listdef 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 Codeif __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 Nodeclass 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 Nodeclass Node { constructor(data) { this.data = data; this.next = null; }}// Function to create a new node with the given datafunction 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 stackfunction 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 listfunction print_list(node) { // Iterate until node is null while (node !== null) { console.log(node.data); node = node.next; }}// Driver Codeconst 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)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
