leetcode刷题记录（六十八）——2. 两数相加

（一）问题描述

2. 两数相加 - 力扣（LeetCode）2. 两数相加 - 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。请你将两个数相加，并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 示例 1：[https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2021/01/02/addtwonumber1.jpg]输入：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] 提示： * 每个链表中的节点数在范围 [1, 100] 内 * 0 <= Node.val <= 9 * 题目数据保证列表表示的数字不含前导零https://leetcode.cn/problems/add-two-numbers/description/?envType=study-plan-v2&envId=top-100-liked给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 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]

提示：

• 每个链表中的节点数在范围 [1, 100] 内
• 0 <= Node.val <= 9
• 题目数据保证列表表示的数字不含前导零

（二）解决思路

        这道题没什么算法，就是对两个链表相加的过程进行模拟。我写的代码不是很精简，但没有任何特殊的计算，就是按照相加过程来写的，很好理解。

• 遍历两列表，至较短列表遍历结束为止，每个对应位置的值相加，并将相加结果放在一个新的链表中；
• 对于两个链表中较长的一个，将其多出来的没有进行相加处理的节点直接放进结果链表里；
• 对于结果链表中的各个节点（除了最后一个节点，最后一个节点如果大于10需要再添加一个节点），如果值大于10，就将其下一个节点的值加一，并将该节点的值减10；
• 对于结果链表中的最后一个节点，如果如果值大于10，就新建一个节点，并将新节点的赋值为1，并将最后一个节点的值减10，否则不动
• 返回结果链表，记得要在处理结果链表之前用一个指针记录结果列表的头节点。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode p1=l1,p2=l2;

        //初始为空节点，方便插入结果节点
        ListNode temp=new ListNode();
        //temp用来移动插入节点，ans记录结果列表的头节点
        ListNode ans=temp;

        //统计两列表公共长度部分的结果节点并插入结果链表
        while(p1!=null&&p2!=null){
          ListNode addNode=new ListNode();
          addNode.val=p1.val+p2.val;
          temp.next=addNode;
          temp=temp.next;
          p1=p1.next;
          p2=p2.next;
        }

        //对于较长的链表，直接将其多出的部分插入结果链表
        while(p1!=null){
          ListNode addNode=new ListNode();
          addNode.val=p1.val;
          temp.next=addNode;
          temp=temp.next;
          p1=p1.next;
        }
        while(p2!=null){
          ListNode addNode=new ListNode();
          addNode.val=p2.val;
          temp.next=addNode;
          temp=temp.next;
          p2=p2.next;
        }
        
        //结果链表去除虚拟头节点
        ans=ans.next;
        //ans处理结果链表，temp记录结果链表的头节点
        temp=ans;
        while(ans.next!=null){
            if(ans.val>=10){
                ans.next.val++;
                ans.val=ans.val-10;
            }
            ans=ans.next;
        }
        //ans剩下最后一个节点
        if(ans.val>=10){
            ListNode lastNode=new ListNode(1,null);
            ans.next=lastNode;
            ans.val=ans.val-10;
        }
        return temp;
    }
}