Multiply Strings

Given two non-negative integers num1 and num2 represented as strings, return the product of num1 and num2. Note:

• The length of both num1 and num2 is < 110.
• Both num1 and num2 contains only digits 0-9.
• Both num1 and num2 does not contain any leading zero.
• You must not use any built-in BigInteger library or convert the inputs to integer directly.

难度：medium

public class Solution {
    private void add(List<Integer> res, List<Integer> tempRes) {
        int i = res.size() - 1, j = tempRes.size() - 1;
        int carry = 0;
        while(i >= 0 && j >=0) {
            int sum = res.get(i) + tempRes.get(j) + carry;
            carry = sum / 10;
            sum %= 10;
            res.set(i, sum);
            --i;
            --j;
        }
        while(i >= 0) {
            int sum = res.get(i) + carry;
            carry = sum / 10;
            sum %= 10;
            res.set(i, sum);
            --i;
        }
        while(j >= 0) {
            int sum = tempRes.get(j) + carry;
            carry = sum / 10;
            sum %= 10;
            res.add(0, sum);
            --j;
        }
        if(carry != 0) {
            res.add(0, carry);
        }
    }
    public String multiply(String num1, String num2) {
        List<Integer> res = new LinkedList<>();
        for(int i = num2.length() - 1; i >= 0; --i) {
            int n2 = num2.charAt(i) - '0';
            int carry = 0;
            List<Integer> tempRes = new LinkedList<>();
            for(int j = num1.length() - 1; j >= 0; --j) {
                int n1 = num1.charAt(j) - '0';
                int mul = n1 * n2 + carry;
                carry = mul / 10;
                mul %= 10;
                tempRes.add(0, mul);
            }
            if(carry != 0) {
                tempRes.add(0, carry);
            }
            for(int k = num2.length() - 1; k > i; --k) {
                tempRes.add(0);
            }
            add(res, tempRes);
        }
        StringBuilder finalRes = new StringBuilder();
        while(res.size() > 1) {
            if(res.get(0) == 0) {
                res.remove(0);
            } else {
                break;
            }
        }
        for(int i = 0; i < res.size(); ++i) {
            finalRes.append(res.get(i).toString());
        }
        return finalRes.toString();
    }
}