【算法】两个数字相加（Add Two Numbers）

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

LeetCode 第2题，通常面试的时候有时候会被这样文档，请设计一个不限制长度的计算器。即为这个问题。

我们顺便学习下英文，程序员必须掌握英文：

给到两个非空的链表来表示两个非负的整数。数字以逆序的方式存储，并且每个节点仅包含一位数字。将两个数字相加返回一个同样结构的链表。

你可以假设数据的数字高位不会是以0开头。

解这个题目有两种思路一种是循环的方式：（这种方式效率相对低耗时较长）

/**
* 数据结构
*/
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
/**
* solution
* Runtime: 4 ms, faster than 50.33% of Java online submissions for Add Two Numbers.
* @param l1
* @param l2
* @return
*/
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode first = l1;
ListNode second = l2;
ListNode current = result;
ListNode previous = result;
// 记录低位到高位的溢出值
int overflowValue = 0;
while (first != null || second !=null) {
if (current == null) {
current = new ListNode();
previous.next = current;
previous = current;
}
// 计算
int firstValue = 0;
if (first != null) {
firstValue = first.val;
}
int secondValue = 0;
if (second != null) {
secondValue = second.val;
}
// 0-19
int tempSum = firstValue + secondValue + overflowValue;
if (tempSum > 9) {
overflowValue = tempSum / 10;
tempSum = tempSum % 10;
current.val = tempSum;
} else {
current.val = tempSum;
overflowValue = 0;
}
if (first != null) {
first = first.next;
}
if (second != null) {
second = second.next;
}
current = current.next;
}
if (overflowValue > 0) {
ListNode last = new ListNode(overflowValue);
current = last;
previous.next = current;
}
return result;
}
@Test
public void test () {
//prepare
ListNode first = new ListNode(9, new ListNode(9,new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
ListNode second = new ListNode(9, new ListNode(9,new ListNode(9, new ListNode(9))));
//execute
ListNode result = addTwoNumbers(first, second);
//verify
while (result != null) {
System.out.print(result.val + "-->");
result =
result.next;
}
System.out.println("");
}

另一种是递归的思想，可以看下我的另一片文章讲解递归的执行。这是一个简单的递归实现：

 /**
* 数据结构
*/
static class ListNode {
int val;
ListNode next;
ListNode() {}
ListNode(int val) { this.val = val; }
ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
/**
* solution
* Runtime: 2 ms, faster than 99.33% of Java online submissions for Add Two Numbers.
* Memory Usage: 42.3 MB, less than 93.16% of Java online submissions for Add Two Numbers.
* @param l1
* @param l2
* @return
*/
public static ListNode addTwoNumbersWithRecursion(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode first = l1;
ListNode second = l2;
ListNode current = result;
ListNode previous = result;
// 记录低位到高位的溢出值
int overflowValue = 0;
add(first, second, current, previous, overflowValue);
return result;
}
static void add(ListNode first, ListNode second, ListNode current, ListNode previous, int overflowValue) {
if (first == null && second == null) {
if (overflowValue > 0) {
ListNode last = new ListNode(overflowValue);
current = last;
previous.next = current;
}
return;
}
if (current == null) {
current = new ListNode();
previous.next = current;
previous = current;
}
// 计算
int firstValue = 0;
if (first != null) {
firstValue = first.val;
}
int secondValue = 0;
if (second != null) {
secondValue = second.val;
}
// 0-19
int tempSum = firstValue + secondValue + overflowValue;
if (tempSum > 9) {
overflowValue = tempSum / 10;
tempSum = tempSum % 10;
current.val = tempSum;
} else {
current.val = tempSum;
overflowValue = 0;
}
if (first != null) {
first = first.next;
}
if (second != null) {
second = second.next;
}
current = current.next;
add(first, second, current, previous, overflowValue);
}
@Test
public void testRecursion () {
//prepare
ListNode first = new ListNode(9, new ListNode(9,new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9, new ListNode(9)))))));
ListNode second = new ListNode(9, new ListNode(9,new ListNode(9, new ListNode(9))));
//execute
ListNode result = addTwoNumbersWithRecursion(first, second);
//verify
while (result != null) {
System.out.print(result.val + "-->");
result =
result.next;
}
System.out.println("");
}

最后

以上就是悲凉钢笔为你收集整理的【算法】两个数字相加（Add Two Numbers）的全部内容，希望文章能够帮你解决【算法】两个数字相加（Add Two Numbers）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。