两个链表相加

问题1

给出两个 非空 的链表用来表示两个非负的整数。l1 = 1->3->4 , l2 = 1->7->4
相加结果为：l = 2->0->9, 可以简单理解为从左向右相加。

原理

• 初始化一个新的链表，定义一个计数器count。
• 循环两个链表，依次相加：(l1.val+l2.val+count)%10; count = (l1.val+l2.val+count)/10;
• 当某个链表为空的时候，默认值为0；当连个链表都为空的时候结束。
• 当count不为0的时候追加到链表尾部。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        int count = 0;
        while(l1!=null||l2!=null){
            int v1 = 0;
            if(l1!=null){
                v1 = l1.val;
                l1 = l1.next;
            }
            int v2 = 0;
            if(l2!=null){
                v2 = l2.val;
                l2 = l2.next;
            }
            run.next = new ListNode((v1+v2+count)%10);
            run = run.next;
            count = (v1+v2+count)/10;
        }
        if(count!=0){
            run.next = new ListNode(count);
        }
        return newHead.next;
    }
}

注意事项

• 注意两个链表为空的情况，要给默认值。
• 注意统计值count不为0的情况，要把count补充到链表的尾部。

问题2

给出两个 非空 的链表用来表示两个非负的整数。l1 = 1->3->4 , l2 = 1->7->4
相加结果为：l = 3->0->8 可以简单理解为从右向左相加。

原理

• 首先，联想到这个问题和第一个问题相比较区别在于：从左到右进位，还是从右到左进位。为了保持和问题一一致，我们应该想办法把问题二倒过来处理，因此可以联想到栈的方式处理。
• 其次，先把两个链表的元素一次进入两个栈里，然后依次从栈里出栈再求和，再采用头插的方式插入新的链表。
• 最后，注意链表为空的情况，注意count不为0的情况。

代码

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1==null){
            return l2;
        }
        if(l2==null){
            return l1;
        }
        ListNode newHead = new ListNode(-1);
        ListNode run = newHead;
        int count = 0;
        Stack<ListNode> stack1 = new Stack<>();
        while(l1!=null){
            stack1.add(l1);
            l1 = l1.next;
        }

        Stack<ListNode> stack2 = new Stack<>();
        while(l2!=null){
            stack2.add(l2);
            l2 = l2.next;
        }

        while(!stack1.isEmpty()||!stack2.isEmpty()){
            int v1 = 0;
            if(!stack1.isEmpty()){
                v1 = stack1.pop().val;
            }
            int v2 = 0;
            if(!stack2.isEmpty()){
                v2 = stack2.pop().val;
            }
            ListNode cur = new ListNode((v1+v2+count)%10);
            cur.next = run.next;
            run.next = cur;

            count = (v1+v2+count)/10;
        }

        if(count!=0){
            ListNode cur = new ListNode(count);
            cur.next = run.next;
            run.next = cur;
        }

        return newHead.next;

    }
}

注意事项

• 注意知识迁移，从问题一迁移到问题二可以联想到栈，在加入新的链表的时候要选择头插法。
• 注意统计值count不为0的情况，要把count补充到链表的尾部。