题目来源

题目描述

用一个 非空 单链表来表示一个非负整数，然后将这个整数加一。

你可以假设这个整数除了 0 本身，没有任何前导的 0。

这个整数的各个数位按照高位在链表头部、低位在链表尾部 的顺序排列。

输入: [1,2,3]
输出: [1,2,4]

题目解析

递归写法

class Solution {
          
   
    struct Info{
          
   
        ListNode *head;
        int carry;

        Info(ListNode *n, int carry): head(n), carry(carry){
          
   

        }
    };


    Info *process(ListNode* l1){
          
   
        if(l1 == nullptr){
          
   
            return new Info(nullptr, 1);
        }

        auto next = process(l1->next);
        int sum = l1->val + next->carry;
        ListNode *newHead = new ListNode(sum % 10);
        newHead->next = next->head;
        return new Info(newHead, sum / 10);
    }
public:
    ListNode* addTwoNumbers(ListNode* l1) {
          
   
        auto info = process(l1);
        ListNode *head = nullptr;
        if(info->carry != 0){
          
   
            head = new ListNode(info->carry);
            head->next = info->head;
        }else{
          
   
            head = info->head;
        }
        return head;
    }
};

类似题目

leetcode：2.逆序链表两数相加 Add Two Numbers