算法：链表相加和大数相加

BM11 链表相加(二)

题目描述

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0 \le n,m \le 10000000≤*n*,*m*≤1000000，链表任意值 0 \le val \le 90≤*v**a**l*≤9
要求：空间复杂度 O(n)*O*(*n*)，时间复杂度 O(n)*O*(*n*)

最优解法：模拟法

import java.util.*;

/*
 * public class ListNode {
 *   int val;
 *   ListNode next = null;
 * }
 */

public class Solution {
    /**
     * 
     * @param head1 ListNode类 
     * @param head2 ListNode类 
     * @return ListNode类
     */
    public ListNode addInList (ListNode head1, ListNode head2) {
        // write code here
        ListNode node1 = reserve(head1);
        ListNode node2 = reserve(head2);
        ListNode node = new ListNode(-1);
        ListNode cur= node;
        int carry = 0;
        int num = 0;
        
        while(node1 != null&&node2 != null){
            num = node1.val+node2.val+carry;
            carry = num/10;
            cur.next = new ListNode(num%10);
            
            cur = cur.next;
            node1 = node1.next;
            node2 = node2.next;
            
        }
        if(node1!=null){
            cur.next = node1;
            while(carry!=0&&cur.next!=null){
                cur.next.val++;
                carry = cur.next.val/10;
                cur.next.val  = (cur.next.val)%10;
                cur = cur.next;
                
            }
            
            
        }
        if(node2!=null){
            cur.next = node2;
            while(carry!=0&&cur.next!=null){
                cur.next.val++;
                carry = cur.next.val/10;
                cur.next.val  = (cur.next.val)%10;
                cur = cur.next;
                
            }
            
            
        }
        ListNode head = reserve(node.next);
        if(carry != 0){
            ListNode temp = new ListNode(1);
            temp.next = head;
            return temp;
        }
        
        return head;
    }
}

addInList可以用以下进行代替(尤其注意while部分)：

public ListNode addInList (ListNode head1, ListNode head2) {
        //任意一个链表为空，返回另一个
        if(head1 == null)
            return head2;
        if(head2 == null)
            return head1;
        //反转两个链表
        head1 = ReverseList(head1);
        head2 = ReverseList(head2);
        //添加表头
        ListNode res = new ListNode(-1);
        ListNode head = res;
        //进位符号
        int carry = 0;
        //只要某个链表还有或者进位还有
        while(head1 != null || head2 != null || carry != 0){
            //链表不为空则取其值
            int val1 = head1 == null ? 0 : head1.val;
            int val2 = head2 == null ? 0 : head2.val;
            //相加
            int temp = val1 + val2 + carry;
            //获取进位
            carry = temp / 10;
            temp %= 10;
            //添加元素
            head.next = new ListNode(temp);
            head = head.next;
            //移动下一个
            if(head1 != null)
                head1 = head1.next;
            if(head2 != null)
                head2 = head2.next;
        }
        //结果反转回来
        return ReverseList(res.next);
    }
}

要点总结:
链表相加可以参考大数加法的解法：大数加法可以直接采用模拟法，原因是String可以方便的从后往前遍历

而链表如果从末位进行相加，是不知道前置节点的，因为没有指针（反转中的pre只是一个标记当前节点的前置节点而已，ListNode本身就没有定义前置指针）

所以链表的解法应该是先将链表进行翻转，最后模拟加完之后再反转回来（开辟一个reserve函数）

BM86 大数加法

import java.util.*;
//因为是大数，所以不能直接进行转换，数据类型会超出范围，通过模拟法逐位相加

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        if(s.equals("")){
            return  t;
        }
        if(t.equals("")){
            return  s;
        }
        //让s成为长的字符串
        if(s.length()<t.length()){
            String temp = t;
            t = s;
            s = temp;
        }
        char[] arr = new char[s.length()];
        int carry = 0;
        int j = t.length() -1;
        for(int i =s.length() -1;i>=0;i--,j--){
            int a = s.charAt(i)-'0'+ carry;
            int b = 0;
            if(j >= 0){
                b = t.charAt(j)-'0';
                
                
            }
            carry = (a+b)/10;
                //int转char要进行强转
            arr[i] = (char)((a+b)%10+'0');
        }
        //转String的一定是char数组，不是int
        String out = String.valueOf(arr);
        if(carry == 1){
            out = "1"+out;
        }
        return out;
    }
}

如果您喜欢此博客或发现它对您有用，则欢迎对此发表评论。也欢迎您共享此博客，以便更多人可以参与。如果博客中使用的图像侵犯了您的版权，请与作者联系以将其删除。谢谢！

算法：链表相加和大数相加

BM11 链表相加(二)

题目描述

addInList可以用以下进行代替(尤其注意while部分)：

要点总结:

BM86 大数加法

特色标签

链友