Add Two Numbers & Add Two Numbers ||

Insert at head (头插法)

Insert at tail (reverse a list) (尾插法) (Add Two Numbers ||)

C++ Member (dot & arrow) Operators

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1);
        //ListNode* prev = dummy;  // compile error
        ListNode* prev = &dummy;
        int carry = 0;

        //for (ListNode* pa = l1, ListNode* pb = l2; // compile error
        //for (ListNode* pa = l1, pb = l2;  // compile error
        for (ListNode* pa = l1, *pb = l2;
             pa != nullptr || pb != nullptr;
             pa = pa == nullptr ? nullptr : pa->next,
             pb = pb == nullptr ? nullptr : pb->next,
             prev = prev->next) {
             //prev = prev->next;) { // compile error

             int a = pa == nullptr ? 0 : pa->val;
             int b = pb == nullptr ? 0 : pb->val;
             int v = (a + b + carry) % 10;
             prev->next = new ListNode(v); \\ Insert at head

             carry = (a + b + carry) / 10;
        }

        if (carry != 0) {
            prev->next = new ListNode(carry);
        }
        //return dummy->next; // compile error!!!!! dummy is not a pointer, cannot be dereferenced
        return dummy.next;
    }
};

Add Two Numbers ||

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

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

Follow up:What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

Method 1: reverse the List

相比于数字为倒序的链表相加问题(add two numbers)，顺序的数字（单向）链表存在处理进位的问题，因为没有反向指针，所以后节点所得的进位，难以加到前一个节点上。 此外，与 add two numbers 问题一样，不能简单地将链表转为整形int或长整型long，因为很有可能超出范围，使用链表的好处正是在于可以几乎无限制地增加number的位数，如果有转换的过程，则很有可能丢失精度。+

因此，最简单的解决办法，就是将 add two numbers ii 问题，转化为 add two numbers 问题：先分别对每个number链表进行反转，然后进行相加，最后将所得链表再进行反转。

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* head1 = reverse(l1);
        ListNode* head2 = reverse(l2);
        ListNode* res = addTwoNumbers1(head1, head2);
        //ListNode* res1 = reverse(res);
        res = reverse(res);
        return res;

       // ListNode* h1 = head1;
       // while (h1) {
       //     cout << h1->val << ' ';
       //     h1 = h1->next;
       // }
       // cout << endl;
       // 
       // return head1;
    }

    ListNode* reverse(ListNode* head) {
        ListNode* prev = nullptr;

        // insert at tail
        while (head != nullptr) {
            ListNode* next = head->next;
            head->next = prev;
            prev = head;
            head = next;
        }
        return prev;
    }

    ListNode* addTwoNumbers1(ListNode* l1, ListNode* l2) {
        ListNode dummy(-1);
        ListNode* prev = &dummy;
        int carry = 0;

        for (ListNode* pa = l1, *pb = l2;
             pa != nullptr || pb != nullptr;
             pa = pa == nullptr ? nullptr : pa->next,
             pb = pb == nullptr ? nullptr : pb->next,
             prev = prev->next) {

             int a = pa == nullptr ? 0 : pa->val;
             int b = pb == nullptr ? 0 : pb->val;
             int v = (a + b + carry) % 10;
             prev->next = new ListNode(v);

             carry = (a + b + carry) / 10;
        }

        if (carry != 0) {
            prev->next = new ListNode(carry);
        }

        return dummy.next;
    }
};

Method 2: stack

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> st1, st2;
        while (l1) {
            st1.push(l1->val);
            l1 = l1->next;
        }
        while (l2) {
            st2.push(l2->val);
            l2 = l2->next;
        }

        ListNode* prev = nullptr;
        int carry = 0;
        while (!st1.empty() || !st2.empty() || carry != 0) {
            int sum = 0;
            if (!st1.empty()) {
                sum = sum + st1.top();
                st1.pop();
            }
            if (!st2.empty()) {
                sum = sum + st2.top();
                st2.pop();
            }
            sum = sum + carry;
            // head Insert
            ListNode* head = new ListNode(sum % 10);
            head->next = prev;
            prev = head;

            carry = sum / 10;
        }

        //if (carry != 0) {
        //    ListNode* head = new ListNode(carry);
        //    head->next = prev;
        //    prev = head;
        //}

        return prev;

    }
};

Bug Version1

/**
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<ListNode*> st1, st2;

        while (l1) {
            st1.push(l1);
            l1 = l1->next;
        }
        while (l2) {
            st1.push(l2);
            l2 = l2->next;
        }

        ListNode dummy(-1);
        ListNode* prev = &dummy;
        int carry = 0;
        while (!st1.empty() || !st2.empty()) {
            ListNode* pa = nullptr;
            ListNode* pb = nullptr;
            if (!st1.empty()) {
                pa = st1.top();
                st1.pop();
            }
            if (!st2.empty()) {
                pb = st2.top();
                st2.pop();
            }
            int a = pa == nullptr ? 0 :pa->val;
            int b = pb == nullptr ? 0 :pb->val;
            int sum = a + b + carry;
            int v = sum % 10;
            prev->next = new ListNode(v);
            prev = prev->next;
            carry = sum /10;
        }
        if (carry != 0) {
            prev->next = new ListNode(carry);
        }

        return dummy.next;
    }
};