445. Add Two Numbers II #

题目 #

给定两个非空链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
思路 #

代码 #

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 int helper(ListNode l1, ListNode l2) {
        if (l1.next == null && l2.next == null) {
            int carry = (l1.val + l2.val) / 10;
            l1.val = (l1.val + l2.val) % 10;
            return carry;
        }
        else {
            int carry = helper(l1.next, l2.next);
            int newCarry = (l1.val + l2.val + carry) / 10;
            l1.val = (l1.val + l2.val + carry) % 10; /** note */
            return newCarry;
        }
    }
    public int addToList(ListNode head, ListNode tail, int carry) {
        if (head == tail) {
            int newCarry = (head.val + carry) / 10;
            head.val = (head.val + carry) % 10;
            return newCarry;
        } else {
            int newCarry = addToList(head.next, tail, carry);
            int result = (head.val + newCarry) / 10;
            head.val = (head.val + newCarry) % 10;
            return result;
        }
    }
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null) return l2;
        if (l2 == null) return l1;
        
        int lenOfL1 = 0, lenOfL2 = 0;
        ListNode ptrOfL1 = l1, ptrOfL2 = l2;
        while(ptrOfL1 != null) { lenOfL1 += 1; ptrOfL1 = ptrOfL1.next; }
        while(ptrOfL2 != null) { lenOfL2 += 1; ptrOfL2 = ptrOfL2.next; }
        
        if (lenOfL1 == lenOfL2) {
            int carry = helper(l1, l2);
            if (carry == 0) return l1;
            else return new ListNode(carry, l1);
        }
        else if (lenOfL1 > lenOfL2) {
            ListNode beforeAlign = l1;
            for (int i=0; i < lenOfL1 - lenOfL2 - 1; i++) beforeAlign = beforeAlign.next;
            int carry = helper(beforeAlign.next, l2);
            if (carry == 0) return l1;
            else {
                int newCarry = addToList(l1, beforeAlign, carry);
                if (newCarry == 0) return l1;
                else return new ListNode(newCarry, l1);
            }
        }
        else {
            ListNode beforeAlign = l2;
            for (int i=0; i < lenOfL2 - lenOfL1 - 1; i++) beforeAlign = beforeAlign.next;
            int carry = helper(beforeAlign.next, l1);
            if (carry == 0) return l2;
            else {
                int newCarry = addToList(l2, beforeAlign, carry);
                int (newCarry == 0) return l2;
                else return new ListNode(newCarry, l2);
            }
        }
    }
}