题目描述

原题链接

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

个人解法

JavaScript

/**
 * Definition for singly-linked list.
 * function ListNode(val, next) {
 *     this.val = (val===undefined ? 0 : val)
 *     this.next = (next===undefined ? null : next)
 * }
 */
/**
 * @param {ListNode} l1
 * @param {ListNode} l2
 * @return {ListNode}
 */
var addTwoNumbers = function(l1, l2) {
    var node = new ListNode('0');
    var head = node;
    var temp = 0;
    while (l1 || l2 || temp) {
        var l1Val = l1 ? l1.val : 0;
        var l2Val = l2 ? l2.val : 0;
        temp = temp + l1Val + l2Val;
        node.next = new ListNode(temp % 10);
        node = node.next;
        temp = parseInt(temp / 10);
        l1 = l1 ? l1.next : l1;
        l2 = l2 ? l2.next : l2;
    };
    return head.next;
};

遇到的问题

1. 当 l1 或 l2 达到链表的尾的时候，需要进行判断，否则会报错
2. 当遇到最后一位要产生进位的时候，我们要判断 temp 的值
3. 获取 l1 或者 l2 的 value 的时候 要判断 是否为空

Java

更优解法

Java

标签：链表
将两个链表看成是相同长度的进行遍历，如果长度不同，则在链表尾部加0；例如输入(2->4->3)+(5->6)，输出(7->0->4)，原因是342+65=407，即(2->4->3)+(5->6->0)。
每次计算需要考虑进位的情况，并实时更新进位值。
如果两个链表都遍历完毕，进位值为1，则需要在链表尾部添加新节点1。
小技巧：对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre=new ListNode(0);
        ListNode cur=pre;
        int carry=0,x,y,sum;
        while(l1!=null||l2!=null){
            if(l1==null)
                x=0;
            else
                x=l1.val;
            if(l2==null)
                y=0;
            else
                y=l2.val;
            sum=carry+x+y;
            carry=sum/10;
            sum=sum%10;
            cur.next=new ListNode(sum);
            cur=cur.next;
            if(l1!=null)
                l1=l1.next;
            if(l2!=null)
                l2=l2.next;
        }
        if(carry==1)
            cur.next=new ListNode(carry);
        return pre.next;
    }
}

画解：

1.

2.

3.

4.

5.

6.

7.

8.

JavaScript

var addTwoNumbers = function(l1, l2) {
    let head = null, tail = null;
    let carry = 0;
    while (l1 || l2) {
        const n1 = l1 ? l1.val : 0;
        const n2 = l2 ? l2.val : 0;
        const sum = n1 + n2 + carry;
        if (!head) {
            head = tail = new ListNode(sum % 10);
        } else {
            tail.next = new ListNode(sum % 10);
            tail = tail.next;
        }
        carry = Math.floor(sum / 10);
        if (l1) {
            l1 = l1.next;
        }
        if (l2) {
            l2 = l2.next;
        }
    }
    if (carry > 0) {
        tail.next = new ListNode(carry);
    }
    return head;
};