算法研究-两数相加

这个系列是笔者练习LeetCode上的算法题的记录&分享

题目

两数相加（Add Two Numbers）

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

题解

1. 需要注意的是两个数组是倒序的
2. 进一位的情况，以及最后一对数字进一位的情况
   例如：[9] + [9] = [8,1]
3. 两组不同位数的值相加

代码

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     public int val;
 *     public ListNode next;
 *     public ListNode(int x) { val = x; }
 * }
 */
public class Solution {
    public ListNode AddTwoNumbers(ListNode l1, ListNode l2) {
        
        int i = 0;
        ListNode r = new ListNode(0);    
        ListNode n = r;
        
        while(l1 != null || l2 != null){
            
            l1 = l1 == null ? new ListNode(0) : l1;
            l2 = l2 == null ? new ListNode(0) : l2;   
            
            n.val = l1.val + l2.val;
            
            n.val += i;            
            
            if(n.val >= 10){
                n.val = n.val - 10;
                i = 1;
            }else{
                i = 0;                
            }
            
            if(l1.next != null || l2.next != null){
                n.next = new ListNode(0);
                n = n.next;                
            }
            
            l1 = l1.next;
            l2 = l2.next;         
            
        };
        
        if(i != 0){
            n.next = new ListNode(i);
            n = n.next;
        }
        
        return r;
    }
}