两数相加
问题描述
给出两个 非空 的链表用来表示两个非负的整数。其中,它们各自的位数是按照 逆序 的方式存储的,并且它们的每个节点只能存储 一位 数字。
如果,我们将这两个数相加起来,则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外,这两个数都不会以 0 开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出:7 -> 0 -> 8
原因:342 + 465 = 807
问题来源:leetcode编程题:两数相加
思考分析
思路:遍历每一种可能出现的"元素对",按照加法原则进行相加,由于加法需要设置一个进位标志。当进行加法运算时,考虑是否有来自地位的进位 和 是否产生进位。
分析可能会出现的情况:
- 如果两个整数位数相同,同时结束两个链表的遍历。
- 如果有其中一个整数的位数较长,其中一个链表先结束遍历,其余的部分为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) {
ListNode* pHead = new ListNode(0); //新链表的头节点指针
ListNode* pNode = pHead; //pNode节点指针对新链表进行操作
bool flag = 0; //进位标志,true表示进位
int sum = 1; //保存相加的结果
//1.遍历每一个节点元素
while ( (l1 != NULL) || (l2 != NULL) )
{//两个链表没有完全遍历结束
if (l1 == NULL)
{//l1代表的链表遍历结束
if (flag) sum = l2->val + 1; //判断是否有进位
else sum = l2->val;
flag = sum/10; //判断是否产生进位
pNode->next = new ListNode(sum%10); //创建节点并写入结果
pNode = pNode->next;
//l1 = NULL; //没有变化
l2 = l2->next;
}
else if (l2 == NULL)
{//l2代表的链表遍历结束
//l1->val为相加的结果
if (flag) sum = l1->val + 1; //判断是否有进位
else sum = l1->val;
flag = sum/10; //判断是否产生进位
pNode->next = new ListNode(sum%10);
pNode = pNode->next;
//l2 = NULL; //没有变化
l1 = l1->next;
}
else
{//l1、l2节点都没有结束
//(l1->val + l2->val)为相加的结果
if (flag) sum = (l1->val + l2->val) + 1; //判断是否有进位
else sum = (l1->val + l2->val);
flag = sum/10; //判断是否产生进位
pNode->next = new ListNode(sum%10);
pNode = pNode->next;
l2 = l2->next;
l1 = l1->next;
}
}
//2.最后判断有无进位
if (flag)
{
//最高位值为1
pNode->next = new ListNode(1);
pNode = pNode->next;
}
pNode->next = NULL;
//返回结果
return (pHead->next);
}
};
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
总结
在coding中,一开始的思路是先创建节点空间 --> 写入当前节点值 --> 偏移下一个节点 --> ... --> 最后返回首节点指针
。但是实现过程中,发现当我将pNode指针偏移到下一个节点,再创建新节点的时候,,之前的创建的节点编程了孤立
节点,不能构成链表。纠结了好半天。。。
看到其他coder的写法,改变了一下顺序,先创建node空间并将当前节点的next指针指向这个node空间,问题就解决了!!! 不过这样首节点就没有意义了,最后返回pHead->next节点。
文章来源: blog.csdn.net,作者:hinzer,版权归原作者所有,如需转载,请联系作者。
原文链接:blog.csdn.net/feit2417/article/details/103114636
- 点赞
- 收藏
- 关注作者
评论(0)