25-链表求和

自己的做法

算法思想

因为是反向存放，个位在首部。所以可以遍历，两个链表对应位置节点相加，构成一个新的节点。

如果值大于等于10，则进位 为1，否则为 0 。

最后遍历结束，如果进位为1，则在链表末尾添加一个值为1的节点。

算法实现

class Solution {
public:
    static ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode * head = new ListNode();
        ListNode * node = head;
        int carry = 0; //进位
        while (l1 != nullptr || l2 != nullptr) {
            int sum = 0;
            if(l1 == nullptr) {
                sum = l2->val + carry;
                l2 = l2->next;
            } else if(l2 == nullptr) {
                sum = l1->val + carry;
                l1 = l1->next;
            } else {
                sum = l1->val + l2->val + carry;
                l1 = l1->next;
                l2 = l2->next;
            }
            ListNode * temp = new ListNode(sum % 10, nullptr);
            node->next = temp;
            node = temp;
            if(sum >= 10) {
                carry = 1;
            } else {
                carry = 0;
            }

        }
        if(carry) {
            ListNode *temp = new ListNode(1, nullptr);
            node->next = temp;
        }
        return head->next;

    }
};

性能分析

时间复杂度：$O(max(n ,m))$，其中n和m分别为两个链表的长度。

空间复杂度：除去需要返回的链表，只用了几个变量。$O(1)$。

参考做法也差不多。

进阶思路

进阶 就是如果数字是正向放的。

可以使用两个栈，先遍历一遍，将链表数字放入栈中。再同时出栈，相加。和反向思路差不多了。