Leetcode2. Add Two Numbers

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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 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(前导零，就是不会有2->4->3->0表示342), except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

结点定义：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}//新标准使用nullptr来给指针赋初值
 * };
 */

优秀代码：

//T(n)=O(max{m,n}),S(n)=O(1)
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(nullptr) {}
 * };
 */
class Solution
{
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
    {
        ListNode dummy(-1); //dummy：虚拟头结点，栈区结点
        int carry = 0;//进位数字位，初始化为0
        ListNode *prev = &dummy;//工作指针指向头结点
        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)
            {
                const int ai = pa == nullptr ? 0 : pa->val;
                const int bi = pb == nullptr ? 0 : pb->val;
                const int value = (ai + bi + carry) % 10;
                carry = (ai + bi + carry) / 10;
                prev->next = new ListNode(value); //尾插法，堆区结点
            }
        if (carry > 0)
            prev->next = new ListNode(carry);
        return dummy.next;//返回第一个有效结点的指针（首结点指针）
    }
};

• 空间复杂度(SpaceComplexity)是对一个算法在运行过程中临时占用存储空间大小的量度。一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。
• 注意：传入和传出的一定是首结点指针（第一个有效元素的地址），比如l1，l2，和dummy.next，而不是头结点指针，因为头结点都是用来简化操作的，而不是实际有意义的；而且，头结点必须用在栈区，因为调用者想要释放堆区的空间，而传出的是首结点，头结点若是堆区，则无法释放，造成内存泄漏。
• 此代码无丝毫瑕疵，逻辑清晰，可读性强，时间复杂度已经最优。
• const int ai = pa == nullptr ? 0 : pa->val;这句代码值得借鉴！