【LeetCode题解---2】Add Two Numbers
【LeetCode题解---2】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 contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.
2
词汇学习
non-empty 非空 non-negative 非负 reverse相反
digits 数字 stored in reverse 反向存储
each of每一个 nodes 节点
3
惊人而又蹩脚的中文翻译
本题主要是类似数据在机器中存储的方式，我们平常所见的数据比如342，在链表中是逆向存储的所以就成了2->4->3这样了，同样5 -> 6 -> 4就是465， 如果这样转换后，我们就会发现342+465=807，在十位上相加是超过10向前进一，但是链表是逆向的，所以就是向后进一。
因此，本题可以把链表中的元素转换为相应的数据后进行相加，得到的结果在按照相应的格式放入链表中,这种方式会很麻烦。应该重新建立一个链表，保存每个节点相加和进位的和。最后应该判断，进位标志位是否任然不为0，这时应该继续创建新的节点，并将进位标志作为节点的值.
4
代码实现-Java
01
解法一
由于加法需要从最低位开始运算，而最低位在链表末尾，链表只能从前往后遍历，没法取到前面的元素，那怎么办呢？
我们可以利用栈来保存所有的元素，然后利用栈的后进先出的特点就可以从后往前取数字了，我们首先遍历两个链表，将所有数字分别压入两个栈s1和s2中，我们建立一个值为0的head节点，然后开始循环，如果栈不为空，则将栈顶数字加入sum中，然后将res节点值赋为sum%10，然后新建一个进位节点point，赋值为sum/10，如果没有进位，那么就是0，然后我们head后面连上res，将res指向head，这样循环退出后，我们只要看res的值是否为0，为0返回res->next，不为0则返回res即可
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 边界条件判断
if (l1 == null) {
return l2;
}else if (l2 == null) {
return l1;
}
ListNode head = new ListNode(0);
ListNode point = head;
int carry = 0;
while (l1 != null && l2 != null) {
int sum = carry + l1.val + l2.val;
ListNode rest = new ListNode(sum % 10);
point.next = rest;
carry = sum / 10;
l1 = l1.next;
l2 = l2.next;
point = point.next;
}
while (l1 != null) {
int sum = carry + l1.val;
ListNode rest = new ListNode(sum % 10);
point.next = rest;
carry = sum / 10;
l1 = l1.next;
point = point.next;
}
while (l2 != null) {
int sum = carry + l2.val;
point.next = new ListNode(sum % 10);
carry = sum / 10;
l2 = l2.next;
point = point.next;
}
if (carry != 0) {
point.next = new ListNode(carry);
}
return head.next;
}02
解法2
遍历两个链表，把各个位数相加，注意进位
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) {
// 边界条件判断
if (l1 == null) {
return l2;
}else if (l2 == null) {
return l1;
}
ListNode list = null;
ListNode next = null;
// 记录和值
int sum = 0;
// 记录是否有进位
int b = 0;
while (l1 != null || l2 != null) {
if (l1 != null) {
sum = l1.val;
l1 = l1.next;
}
if (l2 != null) {
sum += l2.val;
l2 = l2.next;
}
sum += b;
b = sum / 10;
// 如果不利用 / 和 % 的话 此处对于 b 和 sum 的赋值就要根据如下注释掉的方式去做
// 有一丢丢麻烦
// 解法3 中会使用这种方式
/*if (sum > 9) {
// 和值大于9 则代表有进位
sum -= 10;
//b = 1;
} else {
// 无进位
//b = 0;
}*/
if (list == null) {
list = new ListNode(sum % 10);
next = list;
} else {
next.next = new ListNode(sum % 10);
next = next.next;
}
sum = 0;
}
if (b == 1) {
next.next = new ListNode(b);
}
return list;
}03
解法三
只遍历较短的链表，剩下的较长链表可以直接添加
public static ListNode addTwoNumbers3(ListNode l1, ListNode l2) {
// 边界条件判断
if (l1 == null) {
return l2;
}else if (l2 == null) {
return l1;
}
ListNode list = null;
ListNode next = null;
ListNode cl1 = l1.next;
ListNode cl2 = l2.next;
while (true) {
if (cl1 == null) {
cl1 = l1;
cl2 = l2;
break;
} else if (cl2 == null) {
cl1 = l2;
cl2 = l1;
break;
} else {
cl1 = cl1.next;
cl2 = cl2.next;
}
}
int sum = 0;
int b = 0;
while (cl1 != null) {
sum = cl1.val + cl2.val + b;
cl1 = cl1.next;
cl2 = cl2.next;
if (sum > 9) {
sum -= 10;
b = 1;
} else {
b = 0;
}
if (list == null) {
list = new ListNode(sum);
next = list;
} else {
next.next = new ListNode(sum);
next = next.next;
}
sum = 0;
}
next.next = cl2;
while (b == 1) {
if (cl2 == null) {
next.next = new ListNode(b);
break;
}
sum = cl2.val + b;
if (sum > 9) {
sum -= 10;
b = 1;
} else {
b = 0;
}
cl2.val = sum;
cl2 = cl2.next;
next = next.next;
}
return list;
}5
代码实现-Python
- 定义节点。使用：类+构造方法，构造方法的参数要有节点的数值大小、对下一个节点的指针等。
- 若 l1 表示一个链表，则实质上 l1 表示头节点的指针。
- 先实例一个头结点，然后在 while 循环中逐个加入节点
- del ret 删除头结点
代码如下：
#题目中定义的单链表类的结构如下：
#class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
l1,l2为输入的待加和的两个串
"""
#将两个单链表串按位扫到列表listnum1和listnum2中
listnum1 = []
listnum2 = []
while l1 != None:
listnum1.append(l1.val)
l1 = l1.next
while l2 != None:
listnum2.append(l2.val)
l2 = l2.next
#将两个数用整型num1和num2表示出来（**运算为指数运算，eg. 2 ** 3 结果为8）
num1 = 0
num2 = 0
for i in range(len(listnum1)):
num1 = listnum1[i] * (10 ** i) + num1
for j in range(len(listnum2)):
num2 = listnum2[j] * (10 ** j) + num2
#计算结果后，构造结果的单链表结构l3
result = num1 + num2
l3 = ListNode(0)
p = ListNode(0)
p = l3
#l3和p指向首节点，构造过程中l3不动，仍指向首节点，p进行构造移动
while result >= 10:
temp = ListNode(None)
p.val = result % 10
p.next = temp
p = temp
result = result / 10
#由于循环到最后一个节点时不再构造新节点，于是退出循环，并给最后一个节点赋值
p.val = result % 10
return l3以上代码会同步更新在本人的Github和CSDN上
Github地址：https://github.com/Bylant/LeetCode