力扣 445 两数相加II

题目描述

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例1：

输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]

示例2：

输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]

示例3：

输入：l1 = [0], l2 = [0]
输出：[0]

提示：

• 链表的长度范围为 [1, 100]
• 0 <= node.val <= 9
• 输入数据保证链表代表的数字无前导 0

思路分析

和两数相加比起来，这道题的难点在于它不是逆序的而是正序的，这意味着你不能直接在两个链表上进行操作，但可以逆转链表再进行操作，但这样工作量就会很大了，还容易出错。

我做题做了很久，发现一般跟逆序有关系的基本上都可以用栈进行解决，毫无疑问，这里也可以。

这里需要用到三个栈，一个存放链表1，一个放链表2，最后一个用来放和，和之前一样，进位的问题也得单独考虑进去

/**
 * 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%10;
        head->next=temp;
        temp=head;


    }
    return head;
}