数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学将用链表表示的数字加 1？
数字的链表表示方式是，链表的所有节点都被视为数字的一位。节点存储数字的方式是：链表的第一个元素保存数字的最高位，最后一个元素保存数字的最低位。例如，数字 202345 在链表中表示为 (2->0->2->3->4->5)。
要将此链表表示的数字加 1，我们必须检查链表最低位的数值。如果它小于 9，则没有问题；否则，代码将更改下一位数字，以此类推。
现在让我们看一个例子，了解如何操作：1999 表示为 (1->9->9->9)，将 1 加到它应该将其更改为 (2->0->0->0)
Input:1999 Output:2000
解释
将 1 加到用链表表示的给定数字，意味着遵循以下步骤：
- 反转链表：需要反转链表，这意味着将最后一位数字改为第一位，第一位改为最后一位。例如，1->9->9->9 转换为 9->9->9->1。
- 对于此更改后的链表，现在遍历链表，在最左边的节点上加一。如果该节点的值等于 9，则将进位传播到下一个节点。重复此过程，直到没有进位为止。
- 将链表反转回原始形式，然后返回头节点以打印结果。
示例
#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;
}
更新于：2019年8月19日
530 次浏览
广告