个人技术分享

题目描述

两个数都是非负整数，且数的每一位都存储在链表中，求这两个数的和。

解题思路

解法1：循环

每位和进位相加，结果%10存储在链表中。

当某一个链表遍历完的时候，另一个链表没有遍历完全，那么遍历完的链表的元素我们设为0.方便计算。

循环 跳出的条件 ：2个链表的遍历完且进位为0。

为了方便返回，我们用带头的链表。

代码

class Solution {

public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        ListNode* head=new ListNode;

        ListNode* cur=head;

        int c=0;

        while(l1||l2||c)

        {

            int a=l1?l1->val:0,b=l2?l2->val:0;

            int sum=a+b+c;

            c=sum/10;

  

            ListNode* node=new ListNode(sum%10);

            cur->next=node;

            cur=cur->next;

  

            if(l1) l1=l1->next;

            if(l2) l2=l2->next;

        }

        cur=head->next;

        delete head;

        return cur;

    }

};

解法2：递归

2个数相加+进位
这就是一直重复的问题。

提取重复的问题就是一个递归代码。

代码

class Solution {

    int c=0;

public:

    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

        if(!l1&&!l2&&!c) return nullptr;

  

        int sum=(l1?l1->val:0)+(l2?l2->val:0)+c;

        ListNode* head=new ListNode(sum%10);

        c=sum/10;

        head->next=addTwoNumbers(l1?l1->next:nullptr,l2?l2->next:nullptr);

        return head;

    }

};