LeetCode 2 - Add Two Numbers

作者 QIFAN 日期 2017-03-05
LeetCode 2 - Add Two Numbers

原题链接: 2. Add Two Numbers


题干

给两个非空的 Linked List ,分别代表倒序的非负整数,比如 3-->2-->1 代表 123 。同样用 LinkedList 形式返回这两个数字的和。

思路

从前往后分别代表个十百,所以就按照正常的加法运算,和 = A + B + carry ,carry = 和 / 10 ,数字 = 和 % 10

时间复杂度 $O(log(max(M, N)))$ ,空间复杂度 $O(1)$ 。

代码

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
    ListNode res = l1;
    int carry = 0;
    while (l1.next != null && l2.next != null) {
        int sum = l1.val + l2.val + carry;
        l1.val = sum % 10;
        carry = sum / 10;
        l1 = l1.next;
        l2 = l2.next;
    }
    sum = l1.val + l2.val + carry;
    l1.val = sum % 10;
    carry = sum / 10;
    if (l1.next == null) {
        l1.next = l2.next;
    }  

    ListNode pre = l1;
    l1 = l1.next;
    while (l1 != null && carry > 0) {
        int sum = l1.val + carry;
        l1.val = sum % 10;
        carry = sum / 10;
        pre = l1;
        l1 = l1.next;
    }
    if (carry > 0) {
        pre.next = new ListNode(carry);
    }
    return res;
}