LeetCode第2题两数相加

继续打卡算法题，今天学习的是第LeetCode的第2题两数相加，这道题目是道中等题。

分析一波题目

单链表，都需要从头开始遍历，我们可以同时开始遍历两个头节点，创建一个新链表接收新数字，把每位计算的值记录到新的节点，有进位需要保存下来，给下一个节点使用。

同时在使用新链表的时候，一般会使用一个虚拟节点指向头节点，这样可以方便找到头节点。

编码解决

/**
 * 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) {

        if (l1 == null) {
            return l2;
        }
        if(l2 == null) {
            return l1;
        }
        ListNode dumy = new ListNode(-1);
        int bit = 0;
        ListNode last = dumy;
        while(l1 !=null || l2!=null || bit > 0) {
            int v1 = l1 == null ? 0 : l1.val;
            int v2 =  l2==null ? 0: l2.val;
            ListNode l3 = new ListNode(-1);
            //有进位的情况
            if((v1 + v2 + bit) >= 10) {
                l3 = new ListNode((v1 + v2 + bit) % 10);
                //进位存下来
                bit = (v1 + v2 + bit) / 10;
            } else {
                
                l3 = new ListNode(v1 + v2 + bit);
                bit = 0;
            }
            l1 =  l1 == null ? null : l1.next;
            l2 = l2 == null ? null : l2.next;
            last.next = l3;
            last = l3;
        }

        return dumy.next;
    }
}

总结

这个题目就是简单的遍历节点，然后直接相加就可以，时间复杂度O(n)就可以解决