[力扣_2] 两数相加
题目路口:点击进入
相关算法:
链表的基本操作——在此题的时间复杂度为:O(n)
思路与算法:
- 可带头结点和不带头结点,需要一个尾指针每次执行(和链表)的最后一个结点
- 需要判断每次的进位和余位,每次余位由给定两链表的元素值加上前一次计算出来的进位相加%10(小于十的部分)此部分作为此次插入尾端的结点元素值
- 进位由每次给定两链表的元素值加上前一次的进为/10(大于十的部分),此部分为下一次余位进位做准备
- 此外,在两条链表遍历结束后,也许还有剩余的 一条链表,所以需要去判断,同样,在剩余的那条链表上的操作依旧和上述相同,余位和进位只与当前操作链表的值相加获取
- 在两条链表全部遍历结束后,需要判断进位是否还有数值存在,如若存在,需要在尾端再新添一个结点
- 由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。
代码如下:
/**
* Definition for singly-linked list
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
struct ListNode*head=(struct ListNode*)malloc(sizeof(struct ListNode));
head->next=NULL;
struct ListNode*tali=NULL;
struct ListNode*node;
int rame=0,crray=0;
while(l1||l2){
if(l1&&l2){
rame=(crray+l1->val+l2->val)%10;
crray=(crray+l1->val+l2->val)/10;
node=(struct ListNode*)malloc(sizeof(struct ListNode));
node->val=rame;
node->next=NULL;
if(head->next==NULL)
{
head->next=node;
tali=head->next;
}
else
{
tali->next=node;
tali=tali->next;
}
l1=l1->next;
l2=l2->next;
}
if(l1&&l2==NULL)
{
rame=(crray+l1->val)%10;
crray=(crray+l1->val)/10;
node=(struct ListNode*)malloc(sizeof(struct ListNode));
node->val=rame;
node->next=NULL;
tali->next=node;
tali=tali->next;
l1=l1->next;
}
if(l2&&l1==NULL)
{
rame=(crray+l2->val)%10;
crray=(crray+l2->val)/10;
node=(struct ListNode*)malloc(sizeof(struct ListNode));
node->val=rame;
node->next=NULL;
tali->next=node;
tali=tali->next;
l2=l2->next;
}
if(crray>0&&l2==NULL&&l1==NULL)
{
node=(struct ListNode*)malloc(sizeof(struct ListNode));
node->val=crray;
node->next=NULL;
tali->next=node;
tali=tali->next;
}
}
return head->next;
}
A