两数相加

题目

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

解答

package leetcode;
/**
 * 两数相加题 后添加的数字先出来计算，计算结束后先被压在栈底
 * 如果要想像原题那样，我们需要用队列来实现
 */

import Algorithms_again.Stack;


public class TwoNumSum {
    Stack<Integer> p = new Stack<>();
    Stack<Integer> q = new Stack<>();

    public static void main(String[] args) {
        TwoNumSum t = new TwoNumSum(8,8,7,7);
        for (Stack<Integer> s = t.plus(); ! s.isEmpty() ; ) {
            System.out.print(s.pop());
        }
    }

    public Stack<Integer> plus(){
        // 第一步 初始了和
        Stack<Integer> add = new Stack<>();
        int carry = 0;
        while(!p.isEmpty() || !q.isEmpty() ){
            int a = (p.isEmpty())? 0 : p.pop(); // 取出两个数，并处理两个不同位数
            int b = (q.isEmpty())? 0 : q.pop();
            int c = a + b + carry;
            carry = c/10;
            add.push(c % 10); // c/10取余
        }
        if (carry > 0) add.push(carry);
        return add;
    }

    public TwoNumSum(int a, int b, int c, int d) {
        p.push(a);
        p.push(b);
        q.push(c);
        q.push(d);
    }
}