LeetCode——两数相加

NO.2 两数相加中等

思路一：转换法 1.将两个链表先转化成int或long类型数值x和y。2.x和y相加后的值再转换成链表。

缺点：当参数中两个链表足够长时，得到的结果很有可能会超出int或long类型的范围发生溢出。

可以将x和y用BigDecimal类型来存储尽可能避免发生溢出，需要注意的是题目中链表都是逆序的：

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        String s1="";
        String s2="";
        ListNode q=l1,p=l2;
//        将两个链表转化为字符串
        while (q!=null){
            s1=q.val+s1;
            q=q.next;
        }
        while (p!=null){
            s2=p.val+s2;
            p=p.next;
        }
        BigDecimal x=new BigDecimal(s1);
        BigDecimal y=new BigDecimal(s2);
        BigDecimal z=x.add(y);
//        将结果转换成链表
        char[] chars=z.toString().toCharArray();
        ListNode result=new ListNode(Integer.parseInt(String.valueOf(chars[chars.length-1])));
        ListNode t=result;
//        因为链表是逆序的
        for (int i=chars.length-2;i>=0;i--){
            ListNode temp=new ListNode(Integer.parseInt(String.valueOf(chars[i])));
            t.next=temp;
            t=temp;
        }
        return result;
    }

思路二：初等数学法 1.因为链表本身就是逆序的，所以从后向前按位依次加。2.用一个int变量carry来记录前一位相加后得到的进位。3.如果一个链表已经遍历完毕，在后续的按位相加时，该链表的节点值就是0。4.每次按位相加之后更新进位值carry，并将进位之后的数值加入结果链表。5.两个链表遍历相加结束之后，需要再次判断进位值，防止遗漏最高位的进位。

需要注意的是每次按位相加时，不要忘记加上进位值carry。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//        用哑节点来简化代码，如果没有使用哑节点就需要额外的代码来初始化表头的值
        ListNode dummyHead=new ListNode(0);
        ListNode q=l1,p=l2,curr=dummyHead;
//        进位标志carry
        int carry=0;
        while (q!=null||p!=null){
//          获取节点值，如果节点为空，值就为0
            int x=q==null?0:q.val;
            int y=p==null?0:p.val;
//          两个节点值和进位相加
            int sum=x+y+carry;
//          获取相加之后的进位值
            carry=sum/10;
//          将相加后结果加入结果链表
            curr.next=new ListNode(sum%10);
//          移动到下一个节点
            curr=curr.next;
            if (q!=null){
                q=q.next;
            }
            if (p!=null){
                p=p.next;
            }
        }
//        最后判断是否仍有进位，防止进位被遗漏
        if (carry>0){
            curr.next=new ListNode(carry);
        }
//        因为第一个节点是哑节点，
        return dummyHead.next;
    }

时间复杂度：O(max(m,n))

本人菜鸟，有错误请告知，感激不尽！

更多题解和学习记录博客:博客、github

NO.2 两数相加 中等

NO.2 两数相加中等