链表实现两个超大数相加
时间: 2023-07-11 16:21:07 浏览: 51
实现两个超大数相加,可以使用链表来存储这两个数。具体步骤如下:
1. 定义链表节点,包含一个值和指向下一个节点的指针。
```
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
```
2. 将两个超大数分别存储到两个链表中,每个节点存储一位数字。
```
ListNode *num1 = new ListNode(0);
ListNode *num2 = new ListNode(0);
ListNode *p1 = num1, *p2 = num2;
for (int i = 0; i < len1; i++) {
p1->val = num1_str[len1 - 1 - i] - '0';
if (i != len1 - 1) {
p1->next = new ListNode(0);
p1 = p1->next;
}
}
for (int i = 0; i < len2; i++) {
p2->val = num2_str[len2 - 1 - i] - '0';
if (i != len2 - 1) {
p2->next = new ListNode(0);
p2 = p2->next;
}
}
```
其中,`num1_str`和`num2_str`为两个超大数的字符串表示,`len1`和`len2`为它们的长度。
3. 对两个链表进行遍历,依次相加每一位,并将结果存储到新的链表中。
```
ListNode *result = new ListNode(0);
ListNode *p = result;
int carry = 0;
while (num1 || num2) {
int sum = carry;
if (num1) {
sum += num1->val;
num1 = num1->next;
}
if (num2) {
sum += num2->val;
num2 = num2->next;
}
p->val = sum % 10;
carry = sum / 10;
if (num1 || num2 || carry) {
p->next = new ListNode(0);
p = p->next;
}
}
if (carry) {
p->val = carry;
}
```
4. 将新的链表反转,得到相加后的结果。
```
ListNode *rev_result = NULL;
while (result) {
ListNode *next = result->next;
result->next = rev_result;
rev_result = result;
result = next;
}
```
最终,`rev_result`就是两个超大数相加的结果。