1、题目名称

Add Two Numbers （两个链表逐项做带进位的加法生成新链表）

2、题目地址

3、题目内容

英文：You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

中文：给定两个链表，其中的元素都是非负整数。将两个链表的对应位置相加，如果两数相加需要进位，则将进位带到下一组加法。返回相加后的新链表。

例如：给出的链表为（2 -> 4 -> 3）和（5 -> 6 -> 4），则返回的结果为：7 -> 0 -> 8

4、解题方法1

我最开始的思路是，设两个链表为l1和l2，则依次向后遍历两链表。每次遍历都需要考虑以下三点：

1、考虑l1和l2有一个链表里对应位置为空的情况

2、考虑新链表根节点和非根节点的情况

3、考虑进位的情况

一段实现此方法的Java代码如下：

/** * 功能说明：LeetCode 2 - Add Two Numbers * 开发人员：Tsybius * 开发时间：2015年8月27日 */public class Solution {        /**     * 将两个链表逐项相加，生成一个新链表，每次相加和大于10则进位到下一项     * @param l1 链表1     * @param l2 链表2     * @return 新链表     */    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {                ListNode listNodeRoot = null;        ListNode listNodeCurr = listNodeRoot;        int carry = 0;                while (l1 != null || l2 != null)        {            //需要考虑l1和l2有一个为空的情况            int sum = 0;            if (l1 != null) {                sum += l1.val;            }            if (l2 != null) {                sum += l2.val;            }            sum += carry;                        //需要考虑根节点和非根节点的情况            if(listNodeRoot == null)            {                listNodeCurr = new ListNode(sum);                listNodeRoot = listNodeCurr;            }            else            {                listNodeCurr.next = new ListNode(sum);                listNodeCurr = listNodeCurr.next;            }                        //需要考虑进位的情况            carry = 0;            while (listNodeCurr.val >= 10) {                listNodeCurr.val -= 10;                carry += 1;            }                        //向后遍历            if(l1 != null)    {                l1 = l1.next;            }            if(l2 != null)    {                l2 = l2.next;            }        }                //考虑最后一次相加存在进位的情况        if (carry > 0) {            listNodeCurr.next = new ListNode(carry);        }                return listNodeRoot;    }}

不过后来又写出了更简洁的代码，下面这段Java代码的大致思路与之前代码一致，但减少了判断，提高了效率。

/** * 功能说明：LeetCode 2 - Add Two Numbers * 开发人员：Tsybius * 开发时间：2015年8月27日 */public class Solution {        /**     * 将两个链表逐项相加，生成一个新链表，每次相加和大于10则进位到下一项     * @param l1 链表1     * @param l2 链表2     * @return 新链表     */      public ListNode addTwoNumbers(ListNode l1, ListNode l2) {                ListNode listNodeRoot = new ListNode(0);        ListNode listNodeCurr = listNodeRoot;        int carry = 0;                while (l1 != null || l2 != null || carry != 0)        {            //需要考虑l1和l2有一个为空的情况            int sum = (l1 != null ? l1.val : 0) + (l2 != null ? l2.val : 0) + carry;            //计算当前位和进位            listNodeCurr.next = new ListNode(sum % 10);            carry = sum / 10;                        //向后遍历            listNodeCurr = listNodeCurr.next;            l1 = (l1 != null ? l1.next : null);            l2 = (l2 != null ? l2.next : null);        }                return listNodeRoot.next;    }}

附：使用JavaScript语言实现的解题代码（2016年1月23日加入）

/** * @param {ListNode} l1 链表1 * @param {ListNode} l2 链表2 * @return {ListNode} 将两个链表逐项相加，生成一个新链表，每次相加和大于10则进位到下一项 */var addTwoNumbers = function(l1, l2) {    var root = new ListNode(0);    var curr = root;    var carry = 0;    while (l1 !== null || l2 !== null || carry !== 0) {        var sum = (l1 !== null ? l1.val : 0) + (l2 !== null ? l2.val : 0) + carry;        curr.next = new ListNode(sum % 10);        carry = Math.floor(sum / 10);        curr = curr.next;        l1 = (l1 !== null ? l1.next : null);        l2 = (l2 !== null ? l2.next : null);    }    return root.next;};

END