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

本文链接:

https://nullcode.fun/47.html
1 + 3 =
快来做第一个评论的人吧~