[力扣_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

本文链接：