Table of Contents
Explanation
Example
Home Backend Development C++ Add 1 to a number represented by a linked list

Add 1 to a number represented by a linked list

Aug 29, 2023 pm 09:17 PM
number linked list add

Add 1 to a number represented by a linked list

The linked list representation of a number is provided as follows: all nodes of the linked list are considered as one digit of the number. Nodes store numbers such that the first element of the linked list holds the most significant digit of the number, and the last element of the linked list holds the least significant digit of the number. For example, the number 202345 is represented in the linked list as (2->0->2->3->4->5).

To add 1 to this linked list representing numbers, we must check the value of the least significant bit in the list. If it's less than 9 it's ok, otherwise the code will change the next number and so on.

Now let us see an example to understand how to do this, 1999 is represented as (1->9->9 ->9) and adding 1 should change it to (2->0-> 0->0)

Input:1999
Output:2000
Copy after login

Explanation

Add 1 to the number represented by the given linked list, which means you need to follow the following steps:

  • Reverse Linked list: The linked list needs to be reversed, that is, the last number becomes the first, and the first becomes the last. For example, 1->9->9->9 translates to 9->9->9->1.
  • For this reversed linked list, traverse the linked list and add 1 to the leftmost node. If the value of that node is equal to 9, then the carry is passed to the next node. Repeat this process until there are no carries.
  • Restore the string to its original form, then return the head node to print the string.

Example

#include <iostream>
using namespace std;
//n=next node ; d=data ; p= previous node; h=head node; c=current node
class Node {
   public:
      int d;
      Node* n;
};
Node *newNode(int d) {
   Node *new_node = new Node;
   new_node->d = d;
   new_node->n = NULL;
   return new_node;
}
Node *reverse(Node *h) {
   Node * p = NULL;
   Node * c = h;
   Node * n;
   while (c != NULL) {
      n = c->n;
      c->n = p;
      p = c;
      c = n;
   }
   return p;
}
Node *addOneUtil(Node *h) {
   Node* res = h;
   Node *temp, *p = NULL;
   int carry = 1, sum;
   while (h != NULL) {
      sum = carry + h->d;
      carry = (sum >= 10)? 1 : 0;
      sum = sum % 10;
      h->d = sum;
      temp = h;
      h = h->n;
   }
   if (carry > 0)
      temp->n = newNode(carry);
   return res;
}
Node* addOne(Node *h) {
   h = reverse(h);
   h = addOneUtil(h);
   return reverse(h);
}
int main() {
   Node *h = newNode(1);
   h->n = newNode(9);
   h->n->n = newNode(9);
   h->n->n->n = newNode(9);
   h = addOne(h);
   while (h != NULL) {
      cout << h->d;
      h = h->n;
   }
   cout<<endl;
   return 0;
}
Copy after login

The above is the detailed content of Add 1 to a number represented by a linked list. For more information, please follow other related articles on the PHP Chinese website!

Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn

Hot AI Tools

Undresser.AI Undress

Undresser.AI Undress

AI-powered app for creating realistic nude photos

AI Clothes Remover

AI Clothes Remover

Online AI tool for removing clothes from photos.

Undress AI Tool

Undress AI Tool

Undress images for free

Clothoff.io

Clothoff.io

AI clothes remover

AI Hentai Generator

AI Hentai Generator

Generate AI Hentai for free.

Hot Article

R.E.P.O. Energy Crystals Explained and What They Do (Yellow Crystal)
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. Best Graphic Settings
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌
R.E.P.O. How to Fix Audio if You Can't Hear Anyone
2 weeks ago By 尊渡假赌尊渡假赌尊渡假赌

Hot Tools

Notepad++7.3.1

Notepad++7.3.1

Easy-to-use and free code editor

SublimeText3 Chinese version

SublimeText3 Chinese version

Chinese version, very easy to use

Zend Studio 13.0.1

Zend Studio 13.0.1

Powerful PHP integrated development environment

Dreamweaver CS6

Dreamweaver CS6

Visual web development tools

SublimeText3 Mac version

SublimeText3 Mac version

God-level code editing software (SublimeText3)

iOS 17: How to change iPhone clock style in standby mode iOS 17: How to change iPhone clock style in standby mode Sep 10, 2023 pm 09:21 PM

Standby is a lock screen mode that activates when the iPhone is plugged into the charger and oriented in horizontal (or landscape) orientation. It consists of three different screens, one of which is displayed full screen time. Read on to learn how to change the style of your clock. StandBy's third screen displays times and dates in various themes that you can swipe vertically. Some themes also display additional information, such as temperature or next alarm. If you hold down any clock, you can switch between different themes, including Digital, Analog, World, Solar, and Floating. Float displays the time in large bubble numbers in customizable colors, Solar has a more standard font with a sun flare design in different colors, and World displays the world by highlighting

How to add points to Berserker in Dungeon and Fighter Origins How to add points to Berserker in Dungeon and Fighter Origins Mar 17, 2024 am 08:13 AM

How to add points to the berserker in Dungeon and Fighter Origins? The berserker is a mixed-damage profession in the game. In the game, you will face the choice between strength and physical attributes. Which one is more profitable to add first? Regarding the settings of weapons, there are What you need to pay attention to, here is an overview of the priorities for adding points to Berserker attributes in Dungeon and Fighter Origins. Dungeon and Fighter Origins Berserker attribute point priority list 1. Berserker attribute point priority: physical attack power; strength; light attribute enhancement; all attribute enhancement; physical critical hit rate; physical critical hit damage; attack/skill release speed ; Movement speed; Stamina; Spirit. 2. Berserker is a profession that combines fixed damage and percentage damage, which mainly relies on physical attack, strength and independent attack power. 3. Physical attacks will affect solid

C++ program to round a number to n decimal places C++ program to round a number to n decimal places Sep 12, 2023 pm 05:13 PM

Representing numbers as output is an interesting and important task when writing a program in any language. For integer types (data of type short, long, or medium), it is easy to represent numbers as output. For floating point numbers (float or double type), sometimes we need to round them to a specific number of decimal places. For example, if we want to represent 52.24568 as three decimal places, some preprocessing is required. In this article, we will introduce several techniques to represent floating point numbers to a specific number of decimal places by rounding. Among the different approaches, it is important to use a C-like format string, use the precision argument, and use the round() function from the math library. Let’s look at them one by one. with

Find numbers that are not divisible by any number in a range, using C++ Find numbers that are not divisible by any number in a range, using C++ Sep 13, 2023 pm 09:21 PM

In this article, we will discuss the problem of finding numbers between 1 and n (given) that are not divisible by any number between 2 and 10. Let us understand this with some examples - Input:num=14Output:3Explanation:Therearethreenumbers,1,11,and13,whicharenotdivisible.Input:num=21Output:5Explanation:Therearefivenumbers1,11,13,17,and19,whicharenotdivisible. Solved Simple method if

Find the nth node from the last linked list in C++ using recursive method Find the nth node from the last linked list in C++ using recursive method Sep 15, 2023 pm 05:53 PM

Given a singly linked list and a positive integer N as input. The goal is to find the Nth node from the end of the given list using recursion. If the input list has nodes a→b→c→d→e→f and N is 4, then the 4th node from the last will be c. We will first traverse until the last node in the list and when returning from the recursive (backtracking) increment count. When count equals N, a pointer to the current node is returned as the result. Let's look at various input and output scenarios for this - Input - List: -1→5→7→12→2→96→33N=3 Output − The Nth node from the last is: 2 Explanation − The third node is 2 . Input − List: -12→53→8→19→20→96→33N=8 Output – Node does not exist

How to restore WeChat corner mark numbers How to restore WeChat corner mark numbers Nov 29, 2023 pm 05:46 PM

Methods to restore the WeChat corner number: 1. Force quit WeChat and restart; 2. Clear the WeChat cache; 3. Check for WeChat version updates; 4. Uninstall and reinstall WeChat. Detailed introduction: 1. Force quit WeChat and restart. This is the most common method to solve the abnormal number of WeChat corner mark. In the WeChat interface, click the "Me" button in the lower left corner, and then click the "Settings" button in the upper right corner. Open the settings interface. In the settings interface, select "Log out" to log out of WeChat. After a few seconds, start WeChat again. Normally, the corner number will return to normal, etc.

Java program to check if a number is divisible by 5 Java program to check if a number is divisible by 5 Sep 13, 2023 pm 09:01 PM

In mathematics, the divisibility rule of 5 states that if a number ends in 0 or 5, it is divisible by 5. There is another way to determine the divisibility rule of 5, if the remainder is 0, then return the number divisible by 5. The mod(%) operator is commonly used in programming for integer division. Let's give an example. The given number is 525, the number ends with 5 and is divisible by 5. The given number is 7050 which ends with 0 and is divisible by 5. The given number is 678 which does not end with 0 and 5 and is not divisible by 5. In this article, we will solve the question of whether the number is divisible by 5. Algorithm The following steps are where we will use the java.util.* packages to get user input of primitive data types. from main class

Realme GT Neo6 is scheduled to be released on May 9th! The first AI digital human conference in the computer industry Realme GT Neo6 is scheduled to be released on May 9th! The first AI digital human conference in the computer industry May 08, 2024 pm 12:49 PM

On May 7, our mobile phone manufacturer officially announced that our company’s GTNeo6 launch conference is scheduled for May 9. GTNoe6 is positioned as a "performance storm", aiming to stir up the mid-range machine situation. In addition, this conference will also be the first AI digital human conference in the mobile phone industry. At that time, Realme Vice President, Global Marketing President, and China President Xu Qi will appear at the press conference in the form of a digital human. Digital man Xu Qi According to the official introduction, Realme GTNoe6, codenamed "Hurricane", is faster and stronger. It will challenge the strongest third-generation Snapdragon 8s flagship and the strongest product in its class. Recently, the Realme GTNeo6 was found to be directly on the e-commerce platform. Some core configurations were exposed, showing that the machine is not only equipped with a Snapdragon 8s processor, but also supports 120W flash charging.

See all articles