leetcode: Add Two Numbers

问题描述:

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.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

 

原问题链接：https://leetcode.com/problems/add-two-numbers/ 

 

问题分析

    这个问题是一个对加法计算过程的模拟，相对来说比较简单。主要有这么几个要点：

    1. 两个列表都有元素的时候，它们计算的和是(l1.val + l2.val + carry) % 10，carry = (l1.val + l2.val + carry) / 10

    2. 当一个列表没有元素的时候，它们计算的和是(l1.val + carry) % 10, carry = (l1.val + carry) / 10，根据哪个列表有元素设置哪个。

    3. 当两个列表都遍历完之后还要根据进位来判断是否需要新建一个节点。

    4. 因为要返回结果链表，所以需要建立一个临时的节点，并保存它。以后每次计算出一个节点就将它加入到临时节点的后面。最后返回临时节点的后面那个几点作为最终结果。

    根据这个思路，我们可以得到如下的一种实现：

 

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

     这种方式相对来说比较简单直观，但是显得有点冗长。根据问题本身，这里还是有一些可以优化的地方。比如说我们可以不需要在开头定义sum变量，我们可以通过carry变量来计算。另外，根据两个链表判断是否为空的逻辑可以稍微调整一下。我们可以将它修改成两个判断，如果l1 != null, carry += l1.val。如果l2 != null, carry += l2.val。这样在每个判断合格的条件里将l1, l2往后移。这样可以得到一个代码更加简洁的版本：

 

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