关于算法:Leetcode-2题-两数相加

52次阅读

共计 1428 个字符，预计需要花费 4 分钟才能阅读完成。

https://leetcode-cn.com/probl…

给你两个非空的链表，示意两个非负的整数。它们每位数字都是依照逆序的形式存储的，并且每个节点只能存储一位数字。
请你将两个数相加，并以雷同模式返回一个示意和的链表。
你能够假如除了数字 0 之外，这两个数都不会以 0 结尾。

示例如下：

输出：l1 = [2,4,3], l2 = [5,6,4]
输入：[7,0,8]
解释：342 + 465 = 807.

1. 参数是两个链表，两个链表可能蕴含空链表，可能两个链表长度不同，咱们应该将较长的链表遍历完，能力失去最终后果；当长链表没有遍历完，短链表遍历完时，应该补 0 相加；
2. 当两个数字相加之后，咱们应该思考进位，再将进位加到上面两个数相加的和中；
3. 返回后果是链表节点，所以咱们须要定义一个链表节点，为了不便操作，咱们能够建设一个虚构节点，指向真正的和节点，用来不便操作；
4. 最初要判断进位，是否要新建节点。

1. 首先要初始化虚构节点，和节点，进位数字：

ListNode preNode = new ListNode(0);         
ListNode currentNode = preNode;           
int carry = 0;

2. 进入循环，进入循环的条件为，两个链表有一个不为空：
即：

while(l1 != null || l2 != null)

循环外部：
须要有两个数字保留两个链表对应的数值：

int num1 = l1==null?0:l1.val;       
int num2 = l2==null?0:l2.val;

计算和（可能超过 10）：

int sum = num1 + num2 + carry;

计算进位数值和 sum 余 10 后果：

carry = sum / 10;            
sum = sum % 10;

而后建设新节点，让以后节点后移；

currentNode.next = new ListNode(sum);                    
currentNode = currentNode.next;

判断两个链表是否为空，如果不为空，向后挪动；

 if(l1 != null)      
    l1 = l1.next;      
 if(l2 != null)        
    l2 = l2.next;

3. 退出循环后，看进位是否为 0，如果不为 0，再新建节点：

if(carry == 1){currentNode.next = new ListNode(1);
}

残缺代码如下：

/**
 * @user: code 随笔
 */
public class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode preNode = new ListNode(0);
        ListNode currentNode = preNode;
        int carry = 0;

        while(l1 != null || l2 != null){

            int num1 = l1==null?0:l1.val;
            int num2 = l2==null?0:l2.val;

            int sum = num1 + num2 + carry;

            carry = sum / 10;
            sum = sum % 10;

            currentNode.next = new ListNode(sum);
            currentNode = currentNode.next;

            if(l1 != null)
                l1 = l1.next;

            if(l2 != null)
                l2 = l2.next;

        }

        if(carry == 1){currentNode.next = new ListNode(1);
        }

        return preNode.next;
    }
}