题目描述

Add Two Numbers

给定两个非空链表，代表两个非负整数。 数字是按逆序存在链表中，（eg：213，3->1->2) 返回两数相加和的链表

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

另：

• 除了数字 0，其它数字不会以 0起始

From leetcode No.2 Medium (opens new window)

/**
 * 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) {
    
};

解法

点击查看

/**
 * 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) {
    let a = l1.next
    let b = l2.next
    let val1 = l1.val
    let val2 = l2.val
    let flag = 0
    const vals = [(val1 + val2) % 10]
    if (val1 + val2 >= 10)
        flag = 1
    while (a || b) {
        a ? (val1 = a.val, a = a.next) : (val1 = 0, a = null)
        b ? (val2 = b.val, b = b.next) : (val2 = 0, b = null)
        let item = (val1 + val2 + flag) % 10
        if (val1 + val2 + flag >= 10)
            flag = 1
        else
            flag = 0
        vals.push(item)
    }
    let prev = null
    let curr = null
    if (flag)
        prev = new ListNode(1, prev)
    while (vals.length) {
        const val = vals.pop()
        curr = new ListNode(val, prev)
        prev = curr
    }
    return curr
};  

总结

面向错误编程，提交很多次才通过，坑确实有点多

• 直觉思路是把链表对应的两个数字先求和得到sum，再把 sum拆分得到目标链表
  • 但是如果链表过长会出现 sum值溢出的情况，不行
• 解决方案只能是迭代出每个数字，比较大的问题是两个链表长度不一致
  • 一开始实现是只取相同长度部分相加，显然没有考虑到后续多次进位的问题
• 进位的问题
  • 最极端的情况是 [1] 和 [9,9,9,9,9,9,...]的这种组合
• 如何生成最后的目标链表也需要考虑
  • 最简单的是把所有元素存到一个数组里，最后去生成链表。 实现完之后觉得可以改进成一边产生元素，一边生成链表，可减少一次循环

改进版

var addTwoNumbers = function (l1, l2) {
    let a = l1.next
    let b = l2.next
    let val1 = l1.val
    let val2 = l2.val
    let flag = 0
    const ret = new ListNode((val1 + val2) % 10)
    let curr = ret
    if (val1 + val2 >= 10)
        flag = 1
    while (a || b) {
        a ? (val1 = a.val, a = a.next) : (val1 = 0, a = null)
        b ? (val2 = b.val, b = b.next) : (val2 = 0, b = null)
        const item = (val1 + val2 + flag) % 10
        if (val1 + val2 + flag >= 10)
            flag = 1
        else
            flag = 0
        curr.next = new ListNode(item)
        curr = curr.next
    }
    if (flag)
        curr.next = new ListNode(1)
    return ret
};  

看到一个比较好的答案，思路清晰，更好的规避了进位的问题

点击查看

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode c1 = l1;
        ListNode c2 = l2;
        ListNode sentinel = new ListNode(0);
        ListNode d = sentinel;
        int sum = 0;
        while (c1 != null || c2 != null) {
            sum /= 10;
            if (c1 != null) {
                sum += c1.val;
                c1 = c1.next;
            }
            if (c2 != null) {
                sum += c2.val;
                c2 = c2.next;
            }
            d.next = new ListNode(sum % 10);
            d = d.next;
        }
        if (sum / 10 == 1)
            d.next = new ListNode(1);
        return sentinel.next;
    }
}