手撕算法：LeetCode 2.两数想家

题目:LeetCode 2.两数相加

LeetCode链接: LeetCode 2.两数相加 https://leetcode-cn.com/problems/add-two-numbers

审题

边界值问题1：不用考虑0开头。 题目重点：链表表示的每个数就是每个数倒过来，比如：123 3->2->1。

解题

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode p1 = l1;
    ListNode p2 = l2;
    ListNode ret = new ListNode(-1);
    ListNode tmp = ret;
    int carried = 0;
    while(l1!=null || l2!= null){
        int i1 = 0;
        if(l1!=null){
            i1 = l1.val;
            l1 = l1.next;
        }
        int i2 = 0;
        if(l2!=null){
            i2 = l2.val;
            l2 = l2.next;
        }
        int sum = carried + i1 + i2;
        carried = sum/10;
        ListNode next = new ListNode(sum%10);
        tmp.next = next;
        tmp = tmp.next;
    }
    if(carried!=0){
        tmp.next = new ListNode(carried);
    }
    return ret.next;
}

复杂度

• 时间复杂度O(m+n):循环次数，取决于。
• 空间复杂度O(m+n):在进位的情况下，是O((m+n)+1)。

易错点

• 多写几遍就好了
• 13/10=1,13%10=3