[算法]大整数相加

1. 36进制大整数相加

两个36进制的大整数以字符串的形式给出，求出两个大整数的和，并以字符串方式输出。（头条面试题）

比如：12346 + GSFTYHS = GSGW1LY

public class Format36 {
    public static void main(String[] args) {
        System.out.println(sum("12346", "GSFTYHS"));
    }
    
    public static String sum(String num1, String num2){
        String ascii = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        if(num1.length() > num2.length()){
            StringBuilder sb = new StringBuilder(num2);
            for (int i = 0; i < num1.length() - num2.length(); i++) {
                sb.insert(0, '0');
            }
            num2 = sb.toString();
        }
        if(num1.length() < num2.length()){
            StringBuilder sb = new StringBuilder(num1);
            for (int i = 0; i < num2.length() - num1.length(); i++) {
                sb.insert(0, '0');
            }
            num1 = sb.toString();
        }
        
        int add = 0;//进位
        StringBuilder sb = new StringBuilder();
        for (int i = num1.length() - 1; i >= 0; i--) {
            int n1 = ascii.indexOf(num1.charAt(i));
            int n2 = ascii.indexOf(num2.charAt(i));
            int sum = n1 + n2 + add;
            System.out.println(sum);
            sb.insert(0, ascii.charAt(sum % 36));
            add = sum / 36;
        }
        if(add != 0)
            sb.insert(0, add);
        return sb.toString();
    }
}

2. 两个单链表求和

镜像：http://www.cnblogs.com/DarrenChan/p/5724502.html

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

你可以假设除了数字 0 之外，这两个数字都不会以零开头。

进阶:

如果输入链表不能修改该如何处理？换句话说，你不能对列表中的节点进行翻转。

示例:

输入: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
输出: 7 -> 8 -> 0 -> 7

LeetCode：https://leetcode-cn.com/problems/add-two-numbers-ii/description/

思路：

用栈实现：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Stack<ListNode> stack1 = new Stack<>();
        Stack<ListNode> stack2 = new Stack<>();

        while (l1 != null) {
            stack1.push(l1);
            l1 = l1.next;
        }

        while (l2 != null) {
            stack2.push(l2);
            l2 = l2.next;
        }

        int add = 0;// 进位
        int value1 = 0;
        int value2 = 0;
        ListNode ago = null;
        ListNode node = null;
        while (!stack1.isEmpty() || !stack2.isEmpty()) {
            if (!stack1.isEmpty()) {
                value1 = stack1.pop().val;
            } else {
                value1 = 0;
            }

            if (!stack2.isEmpty()) {
                value2 = stack2.pop().val;
            } else {
                value2 = 0;
            }

            int sum = value1 + value2 + add;
            node = new ListNode(sum % 10);
            add = sum / 10;

            node.next = ago;
            ago = node;
        }

        if (add > 0) {
            node = new ListNode(add);
            node.next = ago;
            ago = node;
        }

        return node;
    }

反转单链表实现：

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
        l1 = reverseList(l1);
        l2 = reverseList(l2);

        int add = 0;// 进位
        int value1 = 0;
        int value2 = 0;
        ListNode ago = null;
        ListNode node = null;
        while (l1 != null || l2 != null) {
            if (l1 != null) {
                value1 = l1.val;
                l1 = l1.next;
            } else {
                value1 = 0;
            }

            if (l2 != null) {
                value2 = l2.val;
                l2 = l2.next;
            } else {
                value2 = 0;
            }

            int sum = value1 + value2 + add;
            node = new ListNode(sum % 10);
            add = sum / 10;

            node.next = ago;
            ago = node;
        }

        if (add > 0) {
            node = new ListNode(add);
            node.next = ago;
            ago = node;
        }
        
        //把链表改回来
        l1 = reverseList(l1);
        l2 = reverseList(l2);

        return node;
    }
    
    public ListNode reverseList(ListNode head){
        ListNode pre = null;
        ListNode next = null;
        while(head != null){
            next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }