力扣 445 两数相加II
题目描述
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]示例2：
代码语言：javascript复制输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]示例3：
代码语言：javascript复制输入：l1 = [0], l2 = [0]
输出：[0]提示：
- 链表的长度范围为
[1, 100] 0 <= node.val <= 9- 输入数据保证链表代表的数字无前导 0
思路分析
和两数相加比起来，这道题的难点在于它不是逆序的而是正序的，这意味着你不能直接在两个链表上进行操作，但可以逆转链表再进行操作，但这样工作量就会很大了，还容易出错。
我做题做了很久，发现一般跟逆序有关系的基本上都可以用栈进行解决，毫无疑问，这里也可以。
这里需要用到三个栈，一个存放链表1，一个放链表2，最后一个用来放和，和之前一样，进位的问题也得单独考虑进去
代码语言：javascript复制/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int Stack1[100] = {0};//数组代替栈进行操作
int Stack2[100] = {0};
int top1 = 0;
int top2 = 0;
int sum = 0;
int carry = 0;
struct ListNode* temp = NULL;
struct ListNode* head = NULL;
while (l1) {
Stack1[top1 ] = l1->val;
l1 = l1->next;
}
while (l2) {
Stack2[top2 ] = l2->val;
l2 = l2->next;
}
while (top1 || top2 || carry) {
int n = top1 > 0 ? Stack1[--top1] : 0;
int m = top2 > 0 ? Stack2[--top2] : 0;//考虑到两链表长度不等的情况，不存在的值视作0
sum=n m carry;
carry=sum/10;//求出进位值
head=malloc(sizeof(struct ListNode));
//头插法
head->val=sum;
head->next=temp;
temp=head;
}
return head;
}
