leetCode2两数相加

两数相加

给定两个非空链表来表示两个非负整数。位数按照逆序方式存储，它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。

示例:

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

实现思路

初始化头结点为0; 初始化进位标识为jw=0(当然在循环外的)，然后遍历链表1和链表2，获取相应的值x，y 然后对应的值相加sum=x+y+jw

对sum对10整除，如果>10 则jw进位变更为1（便于在下一轮的循环里加1），然后对10取余代表该节点应该存储的数据

依次次遍历两个链表，为空的时候填充0

最后如果进位>0则代表需要增加一个节点

具体实现

class ListNode{//链表基本结构
    private int val;
    private ListNode next;
    public ListNode() {
    }

    public ListNode( int val ,ListNode next) {
        this.next = next;
        this.val = val;
    }

    public ListNode(int val) {
        this.val = val;
    }
    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public ListNode getNext() {
        return next;
    }

    public void setNext(ListNode next) {
        this.next = next;
    }

    @Override
    public String toString() {
        return "ListNode{" +
                "val=" + val +
                ", next=" + next +
                '}';
    }
}
public class TestDemo {
    @Test
     public void testNode(){
     
        ListNode listNode1=new ListNode(1,new ListNode(4));
        ListNode listNode2=new ListNode(5,new ListNode(6,new ListNode(9,new ListNode(9))));
        System.out.println(listNode1.toString());
        System.out.println(listNode2.toString());
        System.out.println(addTwo(listNode1, listNode2));

     }
    private ListNode addTwo(ListNode listNode1,ListNode listNode2){
        ListNode head=new ListNode(0);
        ListNode l1=listNode1,l2=listNode2;
        ListNode last=head;//位移指针，记录最后的节点位置
        int jw=0;//标识进位
        while (l1!=null||l2!=null){
            int x=(l1!=null) ? l1.getVal():0;
            int y=(l2!=null) ? l2.getVal():0;
            int sum=x+y+jw;
            jw=sum/10;//计算是否进位
            last.setNext(new ListNode(sum%10));
            last=last.getNext();
            if(l1!=null){
                l1=l1.getNext();
            }
            if (l2!=null){
                l2=l2.getNext();
            }
        }
        if(jw>0){//标识最后要进位
             last.setNext(new ListNode(jw));
        }
        return head.getNext();
    }
}

扩展

该思想可以进行大数运算比如整形存不下的数据"123322585555555555555555"+"13212132132123131213"

可以将字符串转换为整形数组，然后进行进位操作，返回字符串具体实现如下

    @Test
     public void  testBigString(){
         System.out.println(addBigString("999","999"));
     }
     public String addBigString(String big1,String big2){
        if(big1==null||big2==null){
            return null;
        }
         char [] r;
         if(big1.length()>big2.length()){
             r=new char[big1.length()+1];
         }else {
             r=new char[big2.length()+1];
         }

        int last=r.length-1;//最后指针
        char [] a=big1.toCharArray();
        char [] b=big2.toCharArray();
        int i=a.length-1;
        int j=b.length-1;
        int jw=0;//进位标识
        while (i>=0||j>=0){
            int x= i>=0 ? (int)(a[i]-'0'):0;
            int y=j>=0 ? (int)(b[j]-'0'):0;
            int sum=x+y+jw;
            jw=sum/10;
            r[last]=(char)(sum%10+'0');
            last--;
            i--;
            j--;
        }
        if(jw>0){
            r[last]=(char)(jw+'0');
        }
         String s=Arrays.toString(r);
        return s.trim();
    }