【LeetCode刷题】2.两数相加

一、问题描述

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.

示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]

示例 3：
输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
输出：[8,9,9,9,0,0,0,1]

问题来源：力扣（LeetCode）

二、代码过程

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    //此方法传入链表l1和链表l2，用于返回满足题目要求的新链表head
        ListNode *head = nullptr, *tail = nullptr;
        //设置新链表head，和表尾指针tail，此时初始化为空
        int tag = 0;
        //设置tag用于进位，初始化进位为0
        while (l1 || l2) {
        //当链表l1和l2不同时为空时，进行循环
            int n1 = l1 ? l1->val: 0;
            int n2 = l2 ? l2->val: 0;
            //n1和n2用于存储当前l1和l2节点的val值
            int sum = n1 + n2 + tag;
            //sum用于存储当前l1和l2节点的val值之和加上tag进位值。
            //链表插入操作
            if (!head) {
            //若为新链表的表头节点，此时直接另表尾指针tail指向表头head，并初始化该节点的val值为sum%10，因为题目中要求每个节点值为1位整数，new ListNode(sum % 10)为创建链表节点的方法
                head = tail = new ListNode(sum % 10);
            } else {
            //若新链表节点不为空，此时直接另表尾结点的下一个节点为新创建的节点new ListNode(sum % 10)，val值为sum % 10。
                tail->next = new ListNode(sum % 10);
                //更新表尾指针，指向表尾
                tail = tail->next;
            }
            //确定进位值，若sum值超过一位整数，则经过sum / 10，进位tag值应该为1
            tag = sum / 10;
            //更新下一个节点，若l1链表不为空，更新
            if (l1) {
                l1 = l1->next;
            }
            //更新下一个节点，若l2链表不为空，更新
            if (l2) {
                l2 = l2->next;
            }
        }
        //若循环结束后，此时还有进位值tag大于0，则创建新节点new ListNode(tag)，链接在表尾
        if (tag > 0) {
            tail->next = new ListNode(tag);
        }
        //返回创建好的head链表
        return head;
    }
};

三、运行结果

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

四、学习总结

1、小技巧设置tag变量，用于控制进位
2、思考问题要全面，插入链表时既要考虑链表为空时的情况，也要考虑链表不为空的情况，缺一不可。删除链表时，既要考虑链表为空的情况，也要考虑正常情况下的删除操作，以及不可以忽略链表只有一个节点时的删除操作，考虑问题要全面，类比到栈和队列的顺序存储和链式存储时的删除插入操作等。
3、此题的算法思想很容易想到，但是容易忽略细节方面的问题，比如一个链表为空另一个不为空时，等待循环结束后，要考虑是否还有进位（容易忽略）等，下次要细心哦，点个赞哇。