题目描述

解题思路

同时遍历两个链表，逐位求和并与当前进位相加（n1 + n2 + carry）,得到新链表对应位置的val = (n1 + n2 + carry) % 10，更新进位值carry = （n1 + n2 + carry）/ 10。
注：

• 当两个链表长度不同时，默认短链表后面有若干个0；
• 遍历结束时，需要判断进位carry是否为0，若不为0，需要在新链表后插入一个节点，节点值为carry。

代码实现

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode l3 = new ListNode(0);
        ListNode root = l3;        //保存链表头位置
        int carry = 0;        //进位值

        int n1,n2;            //l1,l2的当前val
        while(l1 != null || l2 != null){
            if(l1 == null){
                n1 = 0;        //链表为空，val默认为0
            }else{
                n1 = l1.val;
            }
            if(l2 == null){
                n2 = 0;        //链表为空，val默认为0
            }else{
                n2 = l2.val;
            }
            
            ListNode p = new ListNode();
            p.val = (n1 + n2 + carry) % 10;
            l3.next = p;    //尾插法
            l3 = p;
            carry = (n1 + n2 + carry) / 10;        //更新进位值
            if(l1 != null){
                l1 = l1.next;
            }
            if(l2 != null){
                l2 = l2.next;
            }
        }

        if(carry > 0){        //carry不为0,插入节点
            ListNode p = new ListNode();
            p.val = 1;
            l3.next = p;
        }
        
        return root.next;    //新链表的头结点默认为0，从第二个节点处开始返回
    }
}