LeetCode.2-两个数字相加(Add Two Numbers)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

这是悦乐书的第 340 次更新，第 364 篇原创

01 看题和准备

今天介绍的是 LeetCode 算法题中 Medium 级别的第1题（顺位题号是2）。给定两个非空链表，表示两个非负整数。数字以相反的顺序存储，每个节点包含一个数字。将两个数字相加并将其作为链表返回。你可以假设这两个数字不包含任何前导零，除了数字0本身。例如：

输入：（2 -> 4 -> 3）+（5 -> 6 -> 4）

输出：7 -> 0 -> 8

说明：342 + 465 = 807。

本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。

02 第一种解法

计算链表的节点值之和，包含以下两种情况：

进位。两个节点值相加大于等于10后，会产生进位问题，需要将进位产生的数加到下一轮计算上去。如果是在最后一次计算产生进位，结果链表需要增加一个next节点。
两链表的长度不相等时，可能会有一个链表先遍历完节点，而另外一个还剩下许多节点没遍历，因此在遍历的循环条件处，判空是或的关系，直到两个链表的节点都遍历完，才结束循环。

在此解法中，我们使用一个新的链表(头节点值为0)作为结果链表，使用一个boolean类型的变量flag来当做是否有进位的标志。

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    ListNode result = new ListNode(0);

    ListNode tem = l1;

    ListNode tem2 = l2;

    ListNode current = result;

    boolean flag = false;

    while (tem != null || tem2 != null) {

        // 计算节点值之和，需要判空

        int sum = (tem != null ? tem.val : 0) +

                (tem2 != null ? tem2.val : 0);

        // 有进位，节点值之和加1，flag变为false

        if (flag) {

            sum += 1;

            flag = false;

        }

        // 节点值之和大于等于10，只保留个位数，flag变为true

        if (sum >= 10) {

            sum -= 10;

            flag = true;

        }

        current.next = new ListNode(sum);

        current = current.next;

        if (tem != null) {

            tem = tem.next;

        }

        if (tem2 != null) {

            tem2 = tem2.next;

        }

    }

    // 尾节点可能因进位而产生

    if (flag) {

        current.next = new ListNode(1);

    }

    return result.next;

}

03 第二种解法

思路和上面一样，只是将计算进位换了一种方式来实现，采用了取余和整除的方式来实现。

public ListNode addTwoNumbers2(ListNode l1, ListNode l2) {

    ListNode result = new ListNode(0);

    ListNode temp = result;

    int count = 0;

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

        int sum = (l1 == null ? 0 : l1.val) +

                (l2 == null ? 0 : l2.val);

        sum += count;

        count = sum/10;

        temp.next = new ListNode(sum%10);

        temp = temp.next;

        if (l1 != null) {

            l1 = l1.next;

        }

        if (l2 != null) {

            l2 = l2.next;

        }

    }

    if (count > 0) {

        temp.next = new ListNode(count);

    }

    return result.next;

}

04 第三种解法

使用递归。

public ListNode addTwoNumbers3(ListNode l1, ListNode l2) {

    ListNode result = new ListNode(0);

    helper(result, l1, l2, 0);

    return result.next;

}

/**

 * 递归方法

 * @param result 结果链表

 * @param l1

 * @param l2

 * @param carry 进位产生的数

 */

public void helper(ListNode result, ListNode l1, ListNode l2, int carry) {

    if (l1 == null && l2 == null) {

        return ;

    }

    int sum = (l1 == null ? 0 : l1.val) +

            (l2 == null ? 0 : l2.val);

    sum += carry;

    carry = sum/10;

    result.next = new ListNode(sum%10);

    result = result.next;

    if (l1 != null) {

        l1 = l1.next;

    }

    if (l2 != null) {

        l2 = l2.next;

    }

    if (l1 == null && l2 == null && carry > 0) {

        result.next = new ListNode(carry);

    }

    helper(result, l1, l2, carry);

}

05 第四种解法

对上面的递归方法，我们还可以再简化下，不借助额外的递归方法，以此方法本身做递归。

public ListNode addTwoNumbers4(ListNode l1, ListNode l2) {

    if (l1 == null && l2 == null) {

        return null;

    }

    int val = (l1 == null ? 0 : l1.val) +

            (l2 == null ? 0 : l2.val);

    ListNode result = new ListNode(val%10);

    result.next = addTwoNumbers4(l1 == null ? null : l1.next,

            l2 == null ? null : l2.next);

    if (val >= 10) {

        result.next = addTwoNumbers4(result.next, new ListNode(1));

    }

    return result;

}