LeetCode_2_Add Two Numbers

哈妹 lv.1

发布时间：2023-02-02 20:37:39 252

相关标签： # 数据

题目描述：
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

输入样例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

算法思想：将两条链表从头到尾进行遍历，将指针当前所指的节点中的数和进位相加并取余，得到个位数。定义一个进位变量carry，用于标记进位。最后将生成的链表返回即可。

ListNode *head=NULL,*p=NULL;
        int carry=0;
        while(l1||l2){
            int sum1=l1?l1->val:0;
            int sum2=l2?l2->val:0;
            int sum=sum1+sum2+carry;
            carry=sum/10;
            ListNode *cur=new ListNode(sum%10);
            if(!head)
                head=cur;
            if(p)
                p->next=cur;
            p=cur;
            l1=l1?l1->next:NULL;
            l2=l2?l2->next:NULL;
        }
        if(carry){
            ListNode *l=new ListNode(carry);
            p->next=l;
        }
        return head;

以下是运行时间效率图

LeetCode_2_Add Two Numbers_链表

题外话：很长时间没有写链表的算法题目了，手法有点生疏。以下是刚开始写的有点小bug的程序段

ListNode *l3,*p;
        ListNode *head=new ListNode(0); 
        p=l3=head;
        int carry=0;
        while((l1!=NULL)&&(l2!=NULL)){
            int sum=0;
            sum=l1->val+l2->val+carry;
            carry=sum/10;
            sum%=10;
            ListNode* tempNode=new ListNode(sum);
            l3->next=tempNode;
            l3=l3->next;
            l1=l1->next;
            l2=l2->next;
        }
        while(l1!=NULL){
            ListNode* tempNode=new ListNode(l1->val);
            l3->next=tempNode;
            l1=l1->next;
            l3=l3->next;
        }
        while(l2!=NULL){
            ListNode* tempNode=new ListNode(l2->val);
            l3->next=tempNode;
            l2=l2->next;
            l3=l3->next;
        }
        if(carry!=0){
            ListNode* tempNode=new ListNode(carry);
            l3->next=tempNode;
            l3=l3->next;
        }
        head=head->next;
        delete p;
        return head;

网上大神的程序设计：
此算法思想：以l1作为结果链表，最后返回的就是l1的这条链表。将l2中的数据依次加到l1对应的节点上，如果相加后l1->val的值>=10，则说明产生了进位，如果l1->nextNULL，则需要申请节点来存储进位结果，不空则将进位加到next中的val即可。当l1NULL时，只需要将l2剩余的节点连接到l1上即可。
此算法节省了很多时间，而且也节省了很多空间(不需要申请无用的节点了)

class Solution {
public:
  ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    auto l3=l1;
    while(1) {
      if (l1==NULL) {
        return l3;
      }
      if(l2!=NULL) {
        l1->val+=l2->val;
        l2=l2->next;
      }
      if (l1->val>=10) {
        l1->val-=10;
        if (l1->next==NULL) {
          l1->next = new ListNode(1);
        }else {
          l1->next->val++;
        }
      }
      if (l1->next==NULL&&l2!=NULL) {
        l1->next=l2;
        l2=NULL;
      }
      l1=l1->next;
    }
  }
};

运行时间如下图：

LeetCode_2_Add Two Numbers_算法思想_02

文章来源： https://blog.51cto.com/u_15855860/5812165

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。