2/445-两数相加

LeetCode 2. Add Two Numbers

LeetCode-2

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

method: 模拟

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *head = new ListNode(0);
    ListNode *dummy = head;
    int carry = 0;
    while (l1 || l2 || carry) {
        int add1 = l1 ? l1->val : 0;
        int add2 = l2 ? l2->val : 0;
        int sum = add1 + add2 + carry;
        head->next = new ListNode(sum % 10);
        carry = sum / 10;
        head = head->next;
        if (l1) l1 = l1->next;
        if (l2) l2 = l2->next;
    }
    return dummy->next;
}

---

LeetCode 445. Add Two Numbers II

LeetCode-445

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example 1:

Input: l1 = [7,2,4,3], l2 = [5,6,4]
Output: [7,8,0,7]

method: 栈

第2题是从头开始算，这题要从后开始算，所以用到栈

把两个链表的元素取出来放到栈里，然后再一位一位相加。
生成链表的时候使用头插法，插在head前面，head再往前走

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    stack<int> st1;
    stack<int> st2;
    while (l1) {
        st1.push(l1->val);
        l1 = l1->next;
    }
    while (l2) {
        st2.push(l2->val);
        l2 = l2->next;
    }
    ListNode *head = nullptr;
    int sum = 0;
    while (!st1.empty() || !st2.empty() || sum) {
        if (!st1.empty()) {
            sum += st1.top();
            st1.pop();
        }
        if (!st2.empty()) {
            sum += st2.top();
            st2.pop();
        }
        ListNode *node = new ListNode(sum % 10);
        sum /= 10;
        node->next = head;  // 头插法
        head = node;
    }
    return head;
}