【LeetCode】: 两数相加
程序员文章站
2022-06-19 19:38:20
...
给定两个非空链表来表示两个非负整数。位数按照逆序方式存储,它们的每个节点只存储单个数字。将两数相加返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头。
示例:
输入:(2 -> 4 -> 3) + (5 -> 6 -> 4) 输出:7 -> 0 -> 8 原因:342 + 465 = 807
思路:
1.要相加两个数,且这两个数在链表中逆序方式存储,所以我们就要是他们相对应的每一位相加,如下边所示:
- 要使对应的每位相加,则只需要遍历以下链表(用while循环可以完成)
- 将每次对应的位数相加的数定义为 sum
- 需要注意的是每位相加的时候会出现大于10的数这时候就需要进位,则设置这个进位数为 carry = sum / 10
2.在相加每位对应的数时我们需要注意以下几种情况:
3.完成了以上的事情,就需要考虑循环条件了
- 为了使链表遍历一遍就需要条件链表的下一个节点不为空 l->next !=NULL
- 为了考虑到上边第三条出现的情况就得加一条条件 carry == 1
代码部分:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
int sum = 0;
int carry = 0;
struct ListNode* ret = l1;
struct ListNode* ptr = l2;
struct ListNode* new_Node = NULL;
struct ListNode* cur = NULL;
struct ListNode* pre = NULL;
while ((ret != NULL || ptr != NULL) || carry == 1)
{
sum = 0;
if (ret != NULL)
{
sum += ret->val;
ret = ret->next;
}
if (ptr != NULL)
{
sum += ptr->val;
ptr = ptr->next;
}
if(carry != 0)
{
sum += 1;
}
if(sum>9)
{
carry = sum / 10;
}
else
carry = 0;
new_Node = (struct ListNode*)malloc(sizeof(struct ListNode));
new_Node->val = sum % 10;
new_Node->next = NULL;
if(NULL == cur)
{
cur = new_Node;
pre = new_Node;
}
else
{
pre->next = new_Node;
pre = pre->next;
}
}
return cur;
}
复杂度分析:
- 时间复杂度:O(max(m,n))假设上边两链表的长度分别为m,n,则时间复杂度为max(m,n)
- 空间复杂度:O(max(m,n))则新链表的长度最大为max(m,n) + 1
下一篇: 怎么做荷包蛋呢?一起来看看吧