# 2. 两数相加

## 例子

输入：l1 = [2,4,3], l2 = [5,6,4]



输入：l1 = [0], l2 = [0]



输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]



## 提示：

0 <= Node.val <= 9

# V1-简单思路

l1 反转构建为数字

l2 反转构建为数字

num = l1+l2

## java 实现

import java.math.BigInteger;
import java.util.List;
import java.util.ListIterator;

/**
* @author binbin.hou
* @since 1.0.0
* @date 2020-6-9 11:38:48
*/

public 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; }
}

/**
* 最基本思路
* @param l1 列表1
* @param l2 列表2
* @date 2020-6-9 12:08:44
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
List<Integer> numOneList = getIntegerList(l1);
List<Integer> numTwoList = getIntegerList(l2);

BigInteger numOne = buildBigInteger(numOneList);
BigInteger numTwo = buildBigInteger(numTwoList);

return buildListNode(sum);
}

/**
* 构建最后的结果
* @param sum 和
* @return 结果
* @since 1.0.0
*/
private ListNode buildListNode(final BigInteger sum) {
String string = sum.toString();

for(int i = string.length()-2; i >= 0; i--) {
currentNode.next = buildListNode(string, i);
currentNode = currentNode.next;
}

}

private ListNode buildListNode(String string, int index) {
int integer = Integer.parseInt(string.charAt(index) + "");
return new ListNode(integer);
}

/**
* 获取整数的链表
* @param listNode 节点
* @return 结果
* @since 1.0.0
*/
public List<Integer> getIntegerList(ListNode listNode) {
ListNode oneNode = listNode;
while (oneNode != null) {
int value = oneNode.val;
oneNode = oneNode.next;
}
return resultList;
}

/**
* 根据单个数字构建 BigInteger，不知道入参有多长
* @param integers 数组
* @return 结果
* @since 1.0.0
*/
private BigInteger buildBigInteger(final List<Integer> integers) {
integers.iterator();
ListIterator<Integer> iterator = integers.listIterator(integers.size());

// 避免扩容
StringBuilder stringBuilder = new StringBuilder(integers.size());
while(iterator.hasPrevious()){
int integer = iterator.previous();
stringBuilder.append(integer);
}

return new BigInteger(stringBuilder.toString());
}

}


## 效果

Runtime: 18 ms, faster than 5.29% of Java online submissions for Add Two Numbers.
Memory Usage: 40.4 MB, less than 16.38% of Java online submissions for Add Two Numbers.


# V2-记录进位

## java 实现

import java.util.LinkedList;
import java.util.List;

/**
* 官方的解法
*
* 核心：
* 5+7=12 会产生进位，但是最多只有一次进位
* 因为：9+9+1=19
*
* @author binbin.hou
* @since 1.0.0
* @date 2020-6-9 11:38:48
*/

public 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; }
}

/**
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
* Explanation: 342 + 465 = 807.
*
* 注意：
* （1）两个列表并不是一样长的，可能还有数字为空。
* （2）末尾也可能产生进位
*
* 思路：
* 直接遍历链表，使用一个位置保留进位。
*
* 列表的遍历一直是以最长的为准，走到最后。
*
* @param l1 列表1
* @param l2 列表2
* @return 结果
* @date 2020-6-9 12:08:44
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
List<Integer> oneList = getIntegerList(l1);
List<Integer> twoList = getIntegerList(l2);

//[5,5] 最后一位进1
int size = oneList.size() > twoList.size() ? oneList.size() : twoList.size();
// 借助第三条数组，存放进位
int[] overflowFlags = new int[size+1];

// 直接构建结果列表
ListNode headNode = buildListNode(oneList, twoList, 0, overflowFlags);
for(int i = 1; i < size; i++) {
currentNode.next = buildListNode(oneList, twoList, i, overflowFlags);
currentNode = currentNode.next;
}

// 最后如果存在进位的话
if(overflowFlags[size] == 1) {
currentNode.next = new ListNode(1);
}

}

/**
* 构建元素列表
*
* （1）为了避免 index == 0 时，判断
* 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。
* @param oneList 第一个列表
* @param twoList 第二个列表
* @param index 下标
* @param overflowFlags 越界标识
* @return 结果
*/
private ListNode buildListNode(final List<Integer> oneList,
final List<Integer> twoList,
final int index,
int[] overflowFlags) {
int one = getIndexValue(oneList, index);
int two = getIndexValue(twoList, index);

int sum = one + two;
int previousOverflow = overflowFlags[index];

// 一般都是小于 10
int value = sum + previousOverflow;

if(value >= 10) {
overflowFlags[index+1] = 1;
// 保留个位
value -= 10;
}

return new ListNode(value);
}

/**
* 获取下标对应的值
* @param list 列表
* @param index 下标
* @return 值
* @since 1.0.0
*/
private int getIndexValue(final List<Integer> list,
final int index) {
if(index < list.size()) {
return list.get(index);
}

return 0;
}

/**
* 获取整数的链表
* @param listNode 节点
* @return 结果
* @since 1.0.0
*/
private List<Integer> getIntegerList(ListNode listNode) {
ListNode oneNode = listNode;
while (oneNode != null) {
int value = oneNode.val;
oneNode = oneNode.next;
}
return resultList;
}

}


## 效果

Runtime: 3 ms, faster than 29.29% of Java online submissions for Add Two Numbers.
Memory Usage: 42.64 MB, less than 47.4% of Java online submissions for Add Two Numbers.


# V3-优化链表遍历

1）同时遍历两个链表

2）遍历链表的同时，构建节点

## java 实现

import com.github.houbb.leetcode.ListNode;

/**
* 官方的解法
*
* 核心：
* 5+7=12 会产生进位，但是最多只有一次进位
* 因为：9+9+1=19
*
* 核心流程：
*
* @author binbin.hou
* @since 1.0.0
* @date 2020-6-9 11:38:48
*/

/**
* 进位标识
* @since 0.0.1
*/
private static volatile int overflowFlag = 0 ;

/**
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
* Explanation: 342 + 465 = 807.
*
* TODO: 要学会避免前两次的列表循环。
*
* 注意：
* （1）两个列表并不是一样长的，可能还有数字为空。
* （2）末尾也可能产生进位
*
* 思路：
* 直接遍历链表，使用一个位置保留进位。
*
* 列表的遍历一直是以最长的为准，走到最后。
*
*
* @param l1 列表1
* @param l2 列表2
* @return 结果
* @date 2020-6-9 12:08:44
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
overflowFlag = 0;
// 直接构建结果列表

ListNode l1Next = l1.next;
ListNode l2Next = l2.next;
while (l1Next != null || l2Next != null) {
currentNode.next = buildListNode(l1Next, l2Next);
currentNode = currentNode.next;

// 往后遍历
if(l1Next != null) {
l1Next = l1Next.next;
}
if(l2Next != null) {
l2Next = l2Next.next;
}
}

// 最后如果存在进位的话
if(overflowFlag == 1) {
currentNode.next = new ListNode(1);
}

}

/**
* 获取下一个元素值
*
* 默认返回 0
* @param listNode 当前节点
* @return 下一个节点的值
* @since 1.0.0
*/
private int getValue(ListNode listNode) {
if(listNode == null) {
return 0;
}

return listNode.val;
}

/**
* 构建元素列表
*
* （1）为了避免 index == 0 时，判断
* 将 index==0 时的信息直接保存在 0 位，当前进位保存在下一位。
* @param l1 节点1
* @param l2 节点2
* @return 结果
* @since 0.0.1
*/
private ListNode buildListNode(ListNode l1, ListNode l2) {
int valueOne = getValue(l1);
int valueTwo = getValue(l2);

int sum = valueOne+valueTwo + overflowFlag;

if(sum >= 10) {
sum -= 10;
overflowFlag = 1;
} else {
overflowFlag = 0;
}

return new ListNode(sum);
}

}


## 效果

Runtime: 1 ms, faster than 100.00% of Java online submissions for Add Two Numbers.
Memory Usage: 39.7 MB, less than 44.45% of Java online submissions for Add Two Numbers.


# 开源地址

https://github.com/houbb/leetcode