Leetcode:2两数相加

给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。 请你将两个数相加,并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外,这两个数都不会以 0 开头

方法一:递归

定义一个递归函数,参数为两个链表的指针,返回值为链表指针。

  • 思想在于将两个链表指针指向的链表中的第一个元素相加,计算进位值和保留值,创建一个链表节点存储保留值

  • 如果其中任意一个链表的下一个节点存在或当前进位值不为0,说明下一个节点还存在,如果其中一个链表走向尽头就为其创建一个元素为0的节点来延续计算。

  • 两链表指针同时向后移动一位。并且将移动后的两链表指针中的一个指针指向的节点加上进位,进行进位的传递。

  • 将存储保留值的节点的next指向一个新的递归函数

  • 将更新后的两链表指针作为该递归函数的参数

  • 如果两链表均走向尽头且没有进位就退出递归

/*  Definition for singly-linked list.
struct ListNode {
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};
*/
class Solution {
public:
    
    ListNode* Recursive(ListNode* l1, ListNode* l2){
        int carry = (l1->val + l2->val) / 10;
        ListNode* result = new ListNode((l1->val + l2->val)%10); 
        if(l1->next || l2->next || carry)
        {
            l1 = l1->next? l1->next : l1 = (l1->next = new ListNode(0));
            l2 = l2->next? l2->next : l2 = (l2->next = new ListNode(0));
            l1->val += carry;
            result->next = Recursive(l1,l2);
        }
        return result;
    }
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        return Recursive(l1, l2);
    }
};


本文章使用limfx的vscode插件快速发布