给定两个代表非负数的链表，数字在链表中是反向存储的（链表头结点处的数字是个位数，第二个结点上的数字是十位数...），求这个两个数的和，结果也用链表表示。
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出： 7 -> 0 -> 8
[编程题]链表之和
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1==null)
return l2;
if(l2==null)
return l1;
ListNode head = new ListNode(0);
ListNode p = head;
int temp = 0;
while(l1!=null||l2!=null||temp!=0){
if(l1!=null){
temp+=l1.val;
l1=l1.next;
}
if(l2!=null){
temp+=l2.val;
l2=l2.next;
}
p.next=new ListNode(temp%10);
p=p.next;
temp/=10;
}
return head.next;
}
}
发表于 2016-06-07 10:09:26
回复(9)
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null){
return null;
}
int sum = 0;
int c = 0;
ListNode result = new ListNode(0);
ListNode head = result;
while(l1!=null && l2!=null){
sum = l1.val + l2.val + c;
c = sum /10;
head.next = new ListNode(sum%10);
l1 = l1.next ;
l2 = l2.next;
head = head.next;
}
while(l1 != null){
sum = l1.val + c;
c = sum /10;
head.next = new ListNode(sum%10);
l1 = l1.next ;
head = head.next;
}
while(l2 != null){
sum = l2.val + c;
c = sum /10;
head.next = new ListNode(sum%10);
l2 = l2.next ;
head = head.next;
}
if(c != 0){
head.next = new ListNode(1);
}
return result.next;
}
}
发表于 2017-10-16 21:38:03
回复(0)
思考：
其实不用考虑别的，就是两个数字相加，和传统加法唯一的不同就是此题中的加法是从左往右算的，进位也是从左往右进。
例子里给的就是
2 4 3
＋ 5 6 4
——————
7 0 8
正常加法应该先算3+4， 接着4+6，进一位，最后2+5，加之前的进位1，得到8；
在本题就应该先算 2+5， 接着4+6，进一位到3+4中，3+4+1=8，最后得到708。
对于两个list不等长的情况，比如1->8 + 0，就把短的list的末尾用0补齐就行了。
所以我直接遍历两个链表了，取出来的数相加放到新表里。当l1.next或者l2.next == null了，用0替代l1.val或l2.val。
最后还要注意当两个链表都遍历完，相加完之后，如果还有进位，要把进位的数字放到新list的末尾。比如 5 + 5 = 0->1
publicclassSolution {
publicListNode addTwoNumbers(ListNode l1, ListNode l2) {
intplus = 0;
ListNode pl1 = l1;
ListNode pl2 = l2;
ListNode head = null;
ListNode cur = null;
while(plus != 3){
if(pl1 == null&& pl2 == null){
cur.next = plus==0?null:newListNode(plus);
break;
}
intnum1 = (pl1==null)?0:pl1.val;
intnum2 = (pl2==null)?0:pl2.val;
intsum = num1 + num2 + plus;
plus = sum>9?1:0;
sum = sum%10;
if(cur == null){
head = newListNode(sum);
cur = head;
}else{
cur.next = newListNode(sum);
cur = cur.next;
}
pl1 = (pl1==null)?pl1:pl1.next;
pl2 = (pl2==null)?pl2:pl2.next;
}
returnhead;
}
}
发表于 2016-05-15 13:01:19
回复(1)
C++ solution:
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
int carry = 0;
ListNode *root = new ListNode(0), *n = root;
while (l1 != NULL || l2 != NULL || carry) {
int v1 = 0, v2 = 0;
if (l1 != NULL) {
v1 = l1->val;
l1 = l1->next;
}
if (l2 != NULL) {
v2 = l2->val;
l2 = l2->next;
}
int val = (v1 + v2 + carry) % 10;
carry = (v1 + v2 + carry) >= 10 ? 1 : 0;
ListNode *cur = new ListNode(val);
n->next = cur;
n = n->next;
}
return root->next;
}
};
发表于 2018-09-17 19:42:34
回复(0)
- 题目：2. 两数相加
- 难度：中等
- 分类：链表
- 解决方案：链表的遍历
题目描述
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
注意：您可以假设除了数字0之外，这两个数都不会以0开头。
示例：
| 1 2 3 | 输入：(2->4->3) + (5->6->4) 输出：7->0->8 原因：342+465=807 |
分析
这个题理解起来难度不大，就是将数字从个位数开始将数字放到链表的各个结点上，如下所示：
然后两个链表的对应位置上的数字相加，将相加的值保存到结果链表中。这里需要注意两个关键点：一是如果两个值相加大于9该怎么办？二是两个链表长度不一致该怎么办？
对于关键点一：我们需要借助一个进位标识carry，当两数之和大于9时将carry标识为1，否则标识为0。
对于关键点二：我们以最长链表作为终点，对于较短链表对应位置的数值，我们用0来补齐。
下面分析一个具体实例，该实例包含上述两个关键点，如下图所示：
如上图所示，数字342的链表较短，数字7465的链表较长。当两个数字的第二个结点相加时，它们的和为10，这时就需要进位，即carry=1，且将个位数保留作为结果链表的值。当较短的链表指向为null结点时，较长的链表指向的值为7，这需要将较短链表的值设置为0，即结果为0+7。
通过上面分析后，再看看如下java便一目了然。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 创建结果链表的头节点，默认该节点中的value为-1
ListNode dummy = new ListNode(-1);
ListNode pre = dummy;
// 进位标识carry，默认为0
int carry = 0;
// 遍历链表，当两个链表都为空时，退出
while(l1 != null || l2 != null){
// 判断该节点是否为空，当结点为空时，用0补齐；不为空时，加数即为节点的值
int d1 = (l1 == null) ? 0 : l1.val;
int d2 = (l2 == null) ? 0 : l2.val;
// 对结点求和，注意：求和是需要考虑到进位
int sum = d1 + d2 + carry;
// 更新进位标识
carry = (sum >= 10) ? 1 : 0;
// sum%10标识求和的个位数，将其保存到结果链表中
pre.next = new ListNode(sum % 10);
pre = pre.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
// 重点，这是一个特殊情况，当两个链表计算完后，
// 还需要判断进位标识是否为1，如果为1，如23+81=104，需要创建一个结点保存最高位
if(carry == 1)
pre.next = new ListNode(1);
return dummy.next;
}
}
|
对于时间复杂度和空间复杂度，该题都为O(n)。
Github地址
参考链接
更多文章请添加公众号：算法半岛（扫描上图二维码即可关注）
编辑于 2019-06-10 19:17:03
回复(1)
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode result = new ListNode(0);
ListNode preNode = result;
int sum = 0;
ListNode node1 = l1;
ListNode node2 = l2;
while (node1!=null || node2!=null || sum>0){
ListNode node = new ListNode(0);
int val1 = 0;
if (node1 != null){
val1 = node1.val;
node1 = node1.next;
}
int val2 = 0;
if (node2 !=null){
val2 = node2.val;
node2 = node2.next;
}
node.val = (val1+val2+sum)%10;
sum = (val1+val2+sum)/10;
preNode.next = node;
preNode = node;
}
return result.next;
}
}
发表于 2018-05-11 21:06:39
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
//进位
int carry = 0;
// 头结点，不存储结果
ListNode head = new ListNode(0);
ListNode pre = head;
while (l1 != null || l2 != null || carry != 0) {
int sum = (l1 == null ? 0 : l1.val) + (l2 == null ? 0 : l2.val) + carry;
ListNode cur = new ListNode(sum % 10);
carry = sum / 10;
pre.next = cur;
pre = cur;
l1 = (l1 == null ? l1 : l1.next);
l2 = (l2 == null ? l2 : l2.next);
}
return head.next;
}
}
发表于 2017-07-29 12:13:49
回复(0)
import java.math.BigDecimal;
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l2 = reverse(l2);
l1 = reverse(l1);
String s1 = "", s2 = "";
while (l1 != null) {
s1 += l1.val;
l1 = l1.next;
}
while (l2 != null) {
s2 += l2.val;
l2 = l2.next;
}
String sum = new BigDecimal(s1).add(new BigDecimal(s2)).toString();
ListNode dummy = new ListNode(0), p = dummy;
for (int i = 0; i < sum.length(); i ++ ) {
p.next = new ListNode(Integer.valueOf(sum.charAt(i) - '0'));
p = p.next;
}
return reverse(dummy.next);
}
public static ListNode reverse(ListNode head) {
if(head == null || head.next == null) return head;
ListNode pre = head, cur = head.next, temp;
head.next = null;
while (cur != null) {
temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
}
}
发表于 2016-11-18 01:59:28
回复(0)
public ListNode addTwoNumbers (ListNode l1, ListNode l2) {
// write code here
ListNode cur1 = l1;
ListNode cur2 = l2;
ListNode head = new ListNode();
ListNode cur3 = head;
int k; //保存向前进位时的个位数
boolean flag;//判断和是否大于10
while(cur1 != null || cur2 != null){
if(cur1 == null) //当链表1的长度不够时，往后面补0
cur1 = new ListNode(0);
if(cur2 == null)//当链表2的长度不够时，往后面补0
cur2 = new ListNode(0);
int sum = cur1.val + cur2.val;
if(sum >= 10){
k = sum/10;
flag = true;//两个数和大于等于10则记录一下
}else{
k = 0;
flag = false;
}
//两个单链表均向后移动
cur1 = cur1.next;
cur2 = cur2.next;
//如果本次相加大于等于10，则将要进位的数加到后面去，这里加哪个链表的后一个节点都一样，因为不够的链表前面会补0
if(flag){
//这里默认选择链表1的节点扩展，其实选链表2也可以，因为链表长度不一样，前面会自动补0，变成长度一样
if(cur1 == null)//如果两个链表最后一个节点相加的和大于等于10，那么这个链表将扩展一个节点，将节点的数值改成要进位的数
cur1 = new ListNode();
cur1.val = cur1.val + k;
}
cur3.next = new ListNode(sum % 10);//构建一个新链表
cur3 = cur3.next;
}
return head.next;//头结点要存数据，所以去掉不存数据的头结点
}
发表于 2020-07-20 19:29:19
回复(0)
class Solution {
public:
/**
*
* @param l1 ListNode类
* @param l2 ListNode类
* @return ListNode类
*/
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
// write code here
if(!l1 || !l2) return l1 ? l1 : l2;
auto *head = l1;
int carry = 0;
while(l1 || l2){
l1->val += l2 ? l2->val + carry : carry;
carry = l1->val / 10;
l1->val %= 10;
if(!l1->next && l2) l1->next = l2->next, l2->next = nullptr;
if(!l1->next && carry) l1->next = new ListNode(1), l1 = l1->next;
l1 = l1->next;
l2 = l2 ? l2->next : l2;
}
return head;
}
};
发表于 2020-07-11 09:13:38
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null)
return l2;
if(l2 == null)
return l1;
int sum = 0;
int jinwei = 0;//用来做进位的,往右进位
ListNode p = new ListNode(-1);
ListNode head = p;
while(l1 != null || l2 != null || jinwei != 0) {
//l1和l2直接按位加起来
if(l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if(l2!=null) {
sum += l2.val;
l2 = l2.next;
}
//再把进位加上
sum += jinwei;
p.next = new ListNode(sum%10);
p = p.next;
jinwei = sum / 10; //除以10用来下次循环进位
sum = 0; //清零等下次循环再相加
}
return head.next;
}
}
发表于 2019-12-10 10:42:59
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null) {
return null;
}
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
int carry = 0;
while (l1 != null || l2 != null) {
int num1 = (l1 == null) ? 0 : l1.val;
int num2 = (l2 == null) ? 0 : l2.val;
int sum = num1 + num2 + carry;
carry = sum / 10;
cur.next = new ListNode(sum % 10);
cur = cur.next;
if (l1 != null) {
l1 = l1.next;
}
if (l2 != null) {
l2 = l2.next;
}
}
if (carry > 0) {
cur.next = new ListNode(carry);
}
return dummy.next;
}
}
发表于 2019-11-04 17:25:32
回复(0)
分享一个递归的写法。用默认参数cnt保存进位。如果链表不空或者进位不等于0，就把这些值加到sum。然后构造节点，构造节点的next指向下一层递归。
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2, int cnt = 0)
{
if (l1 == nullptr && l2 == nullptr && cnt == 0)
return nullptr;
int sum = cnt;
if (l1 != nullptr)
{
sum += l1->val;
}
if (l2 != nullptr)
{
sum += l2->val;
}
ListNode *res = new ListNode(sum % 10);
res->next = addTwoNumbers(l1 ? l1->next : l1, l2 ? l2->next : l2, sum / 10);
return res;
}
发表于 2019-08-14 19:09:39
回复(0)
- 增加一个整数carry就可以模拟数字相加了
public static ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
// 先用堆栈存起来
Stack<Integer> num1 = new Stack<>();
Stack<Integer> num2 = new Stack<>();
while (l1 != null) {
num1.push(l1.val);
l1 = l1.next;
}
while (l2 != null) {
num2.push(l2.val);
l2 = l2.next;
}
int carry = 0; // 表示进位
ListNode res = new ListNode(0);
while (!num1.isEmpty() && !num2.isEmpty()) {
ListNode tmp = new ListNode(num1.pop() + num2.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
// 清掉num1
while (!num1.isEmpty()) {
ListNode tmp = new ListNode(num1.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
// 清掉num2
while (!num2.isEmpty()) {
ListNode tmp = new ListNode(num2.pop() + carry);
if (tmp.val>=10) {
carry = tmp.val / 10;
tmp.val = tmp.val % 10;
} else {
carry = 0;
}
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
if (carry != 0) {
ListNode tmp = new ListNode(carry);
// 结果链表插入新节点
tmp.next = res.next;
res.next = tmp;
}
return res.next;
}
另外提供镜像题目的解，即链表和结果都是最高位在前的：Add Two Numbers II,思路就是借助stack来进行逆序操作
public static ListNode addTwoNumbers2(ListNode l1, ListNode l2) { // 结果链表 ListNode res = new ListNode(0); ListNode cur = res; int carry = 0; // 记录进位情况 while (l1 != null && l2 != null) { ListNode tmp = new ListNode(l1.val + l2.val + carry); if (tmp.val>=10) { carry = tmp.val / 10; tmp.val = tmp.val % 10; } else { carry = 0; } // 结果链表插入新节点 cur.next = tmp; cur = cur.next; l1 = l1.next; l2 = l2.next; } // 清空num1 while (l1 != null) { ListNode tmp = new ListNode(l1.val + carry); if (tmp.val>=10) { carry = tmp.val / 10; tmp.val = tmp.val % 10; } else { carry = 0; } // 结果链表插入新节点 cur.next = tmp; cur = cur.next; l1 = l1.next; } // 清空num2 while (l2 != null) { ListNode tmp = new ListNode(l2.val + carry); if (tmp.val>=10) { carry = tmp.val / 10; tmp.val = tmp.val % 10; } else { carry = 0; } // 结果链表插入新节点 cur.next = tmp; cur = cur.next; l2 = l2.next; } // 清掉carry if (carry != 0) { ListNode tmp = new ListNode(carry); // 结果链表插入新节点 cur.next = tmp; cur = cur.next; } return res.next; }
发表于 2019-02-27 15:13:47
回复(0)
public class Solution {
/*
* 思考：
* 本题两个数字相加和传统加法唯一的不同就是此题的加法是从左往右算的，进位也是从左往右进。
* 例子里给的就是
2 4 3
+ 5 6 4
——————————
7 0 8
* 正常加法应该先算3+4，接着4+6，进一位，最后2+5，加之前的进位1，得到8；
* 在本题就应该先算2+5，接着4+6，进一位到3+4中，3+4+1=8，最后得到708。
*/
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if(l1 == null) return l2;
if(l2 == null) return l1;
ListNode head = new ListNode(0); //用来存计算结果的链表头
ListNode p = head; //计算过程中移动使用的动态指针
int temp = 0; //用来暂存每次计算结果的临时变量
while(l1!=null || l2!=null || temp!=0) {
if(l1 != null) {
temp += l1.val;
l1 = l1.next;
}
if(l2 != null) {
temp += l2.val;
l2 = l2.next;
}
p.next = new ListNode(temp%10);
p = p.next;
temp /=10; //temp除10的结果，其实就是进位
}
return head.next;
}
发表于 2019-01-02 11:54:48
回复(0)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
ListNode *L = new ListNode(0);
ListNode *p = L;
int x = 0;
while(l1 || l2 || x)
{
if(l1)
{
x += l1->val;
l1 = l1->next; } if(l2) { x += l2->val; l2 = l2->next; } p->next = new ListNode(x%10); p = p->next; x /= 10; } return L->next;
}
};
发表于 2017-09-21 01:15:03
回复(0)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
ListNode* ret = new ListNode(-1);
ListNode* result = ret;
int carry = 0;
while(l1 != NULL && l2 != NULL)
{
int sum = l1->val + l2->val + carry;
if(sum >= 10)
{
carry = 1;
sum = sum - 10;
}
else
{
carry = 0;
}
ret->next = new ListNode(sum);
ret = ret->next;
l1 = l1->next;
l2 = l2->next;
}
while(l1 != NULL)
{
int sum = l1->val + carry;
if(sum >= 10)
{
carry = 1;
sum = sum - 10;
}
else
{
carry = 0;
}
ret->next = new ListNode(sum);
ret = ret->next;
l1 = l1->next;
}
while(l2 != NULL)
{
int sum = l2->val + carry;
if(sum >= 10)
{
carry = 1;
sum = sum - 10;
}
else
{
carry = 0;
}
ret->next = new ListNode(sum);
ret = ret->next;
l2 = l2->next;
}
if(carry == 1)
{
ret->next = new ListNode(carry);
ret = ret->next;
}
return result->next;
}
};
发表于 2017-09-19 23:05:16
回复(0)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) {
* val = x;
* next = null;
* }
* }
*/
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode res = new ListNode(0);
ListNode tail = res;
while(!(l1 == null && l2 == null && carry == 0)){
int x = l1 != null ? l1.val : 0;
int y = l2 != null ? l2.val : 0;
int sum = x + y + carry;
carry = sum / 10;
ListNode newNode = new ListNode(sum % 10);
tail.next = newNode;
tail = newNode;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
return res.next;
}
}
发表于 2017-08-09 16:34:54
回复(1)
class Solution(object):
def addTwoNumbers(self, l1, l2):
"""
:type l1: ListNode
:type l2: ListNode
:rtype: ListNode
"""
result = ListNode(0)
root = result
while(l1!=None or l2!=None):
l1 = l1 if l1 is not None else ListNode(0)
l2 = l2 if l2 is not None else ListNode(0)
result.val += l1.val + l2.val
if(result.val>=10):
result.val %= 10
result.next = ListNode(1)
elif(l1.next!=None or l2.next!=None):
result.next = ListNode(0)
result = result.next
l1 = l1.next if l1 is not None else None
l2 = l2.next if l2 is not None else None
return root
发表于 2017-08-05 17:34:34
回复(0)
class Solution {
public:
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2)
{
ListNode fake(0);
ListNode *p = &fake;
int carry = 0;
while(l1 || l2 || carry)
{
int sum = (l1?l1->val:0)+(l2?l2->val:0)+carry;
carry = sum/10;
p->next = new ListNode(sum%10);
p = p->next;
l1 = l1 ? l1->next : nullptr;
l2 = l2 ? l2->next : nullptr;
}
return fake.next;
}
};
发表于 2017-07-11 19:46:36
回复(0)
问题信息
难度：
95条回答
56收藏
21040浏览
通过挑战的用户
查看代码-
2022-08-20 17:12:53
-
2022-08-11 00:25:49 -
2022-06-19 19:30:18
-
2022-06-01 12:15:58 -
2022-05-24 13:24:12
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
