LeetCode刷题笔记（Java实现）-- 2. 两数相加

LeetCode刷题笔记（Java实现）-- 2. 两数相加

题目难度：Medium

题目要求

##解法分析
首先，初始化一个新的空的链表，进位也初始化为0；
如果，节点L1非空或者L2非空，就是还可以继续相加的话，就进入循环；
循环{
如果当前值不为空，就取该位置的数，否则就赋值为0，即保证两链表长度相等，不足的补0；
求和即将两个链表相同位置的数相加，还要加上进位数！！！
如果头、尾节点为空，就把求的和整除10后的余数生成新节点后，赋值给头、尾节点，第一个节点就生成了；
如果头、尾节点不为空，尾节点的next指针指向新生成的节点，尾节点后移一位；
进位数=sum/10;
节点L1和L2分别后移一位，开始新一位相加
}
最后，如果进位数还有值，最多也就是1，就把该进位数赋值给一个新的节点；
返回新生成链表的头节点。

注：java链表的学习，参考：https://blog.csdn.net/qq_41437542/article/details/108768900

##代码示例

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode head = null;
            ListNode tail = null;
            int carry = 0; //进位
            while(l1!=null||l2!=null){
                int n1=l1!=null?l1.val:0;
                int n2=l2!=null?l2.val:0;
                int sum = n1 + n2 + carry;
                if(head == null){
                    tail=new ListNode(sum % 10);
                    head = tail;
                }else{
                    tail.next=new ListNode(sum % 10);
                    tail=tail.next;
                }
                carry = sum / 10;
                if(l1!=null){
                    l1=l1.next;
                }
                if(l2!=null){
                    l2=l2.next;
                }
            }
            if(carry>0){
                tail.next=new ListNode(carry);
            }
            return head;
    } 
}

复杂度分析：

时间复杂度：
O(max(m,n))，其中 m 和 n分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

空间复杂度：
O(1)。注意返回值不计入空间复杂度。