2.两数相加

题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

示例

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

题解

包含多位的数字，每个位置上的元素逆序放入一个链表中，一共有两个数字，所以两个链表；
每位数字的相加，进行余数和进位数的处理；
链表构造采用尾插法；

注意事项

• 余数和进位的处理
• 如果在构造链表时，尾部元素不好获得可以引入 tail 尾指针
• 头指针 在为 null 时进行处理，在 while 多次循环时不处理，只处理 tail 尾指针，构造链表采用尾插法
• 在 while 循环中，头指针元素和后来元素的链接需要单独处理
• 数组长短不一致，数组短的剩余元素补零
• 非 null 判断，才能获取它的 next 节点
• 临界情况处理，比如参与计算的数组1和数组2的长度不相等的处理
• 最后一位，进位成功，放入链表末尾的处理

复杂度分析

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

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

        ListNode head = null;
        ListNode tail = null;
        ListNode head1 = l1;
        ListNode head2 = l2;
        int jinWei = 0;
        while(head1 != null || head2 != null){
            int node1Value = head1 != null ? head1.val : 0 ;
            int node2Value = head2 != null ? head2.val : 0 ;
        
            int yuShu = (node1Value + node2Value + jinWei) % 10;
            jinWei = (node1Value + node2Value + jinWei) / 10;
            ListNode first = new ListNode();
            first.val = yuShu;
            if (head == null){
                head = first;
                tail = first;
            } else {
                tail.next = first;
                tail = first;
            }
            if(head1 != null){
                head1 = head1.next;
            }
            if(head2 != null){
                head2 = head2.next;  
            }
            
        }
        if(jinWei != 0){
            ListNode last = new ListNode();
            last.val = jinWei;
            tail.next = last;
            tail = last;
        }
        return head;
    }
}