题号：2
难度：Medium
链接：https://leetcode.cn/problems/add-two-numbers

思路

一开始想直接拼成字符串，翻转后转成整数，运算完再还原。但本题中节点数在100以内，没有合适的整型能用，于是还得逐个节点处理。

后来想用递归，但直接写递归越写越乱，虽然能跑，但数据实在难看。

最后还是老老实实分步做。

本题不要求两个输入链表保持原样，为了节约空间，直接将结果存在长的那个链表上，并返回。

首先确定两个链表的长短关系，这需要O(n)。

然后分为三步：

第一步，处理与短链表等长的部分，逐节点相加（包括进位），存在长链表上。

第二步，处理长链表中超出短链表的部分，主要是进位的问题。

第三步，处理长链表的尾部。因为可能会多一个进位，需要另构造一个节点加上去。

代码

#include <algorithm>

using std::swap;

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:
    // 为了节约new使用的空间和时间，直接把较长的链表加到较短的链表上去
    //为此需要判断哪个长哪个短
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        //首先确定两个链的长短
        int longLen=0,shortLen=0;
        //假设l1长
        ListNode* pos=l1,*longList=l1,*shortList=l2;
        while(pos!=nullptr){
            ++longLen;
            pos=pos->next;
        }
        pos=l2;
        while (pos!=nullptr)
        {
            ++shortLen;
            pos=pos->next;
        }
        //反了就交换
        if(longLen<shortLen){
            swap(longLen,shortLen);
            swap(longList,shortList);
        }
        ListNode* l3=longList;

        //开始分段处理
        int forwardNum=0; //进位
        ListNode* tail;//标出长链的尾巴
        //第一段
        //短链部分
        for(;shortList!=nullptr;shortList=shortList->next,longList=longList->next){
            longList->val += shortList->val + forwardNum;
            forwardNum=longList->val/10;
            longList->val %= 10;
            tail = longList;
        }
        //第二段
        //长链超出短链的部分
        for(;forwardNum!=0&&longList!=nullptr;longList=longList->next){
            longList->val += forwardNum;
            forwardNum = longList->val/10;
            longList->val %= 10;
            tail = longList;
        }
        //第三段
        //补上长链的尾巴
        if(forwardNum!=0){
            ListNode* temp = new ListNode;
            tail->next=temp;
            temp->val = forwardNum;
        }
        return l3;
    }
};

提交结果

时间、空间表现都不错，但是代码还是长了点。

dalao解法

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode root = new ListNode(0);
        ListNode cursor = root;
        int carry = 0;
        while(l1 != null || l2 != null || carry != 0) {
            int l1Val = l1 != null ? l1.val : 0;
            int l2Val = l2 != null ? l2.val : 0;
            int sumVal = l1Val + l2Val + carry;
            carry = sumVal / 10;

            ListNode sumNode = new ListNode(sumVal % 10);
            cursor.next = sumNode;
            cursor = sumNode;

            if(l1 != null) l1 = l1.next;
            if(l2 != null) l2 = l2.next;
        }

        return root.next;
    }
};

虽然是循环版，但dalao还是强，简洁易懂。这里实际将两个链表视为等长，另用两个int值存储节点值，空节点则值为0，这样就不必考虑哪个链表长，哪个链表短。

改成递归也容易：

class Solution {
public:
  ListNode addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* l3;
    return l3 = add(l1,l2);
  }
  ListNode* add(ListNode* l1,ListNode* l2,int forwardNum=0){
    if(l1!=nullptr||l2!=nullptr||forwardNum!=0){
      int val_1 = l1==nullptr?0:l1->val;
      int val_2 = l2==nullptr?0:l2->val;
      int sum_val = val_1+val_2+forwardNum;
      forwardNum=sum_val/10;
      ListNode* temp = new ListNode(sum_val%10);
      if(l1!=nullptr) l1=l1->next;
      if(l2!=nullptr) l2=l2->next;
      temp->next = add(l1,l2,forwardNum);
      return temp;
    }
  }
};

没测试过，应该没问题。

看来以后应该先把循环解法弄明白、写简洁，再去考虑递归法，不然脑子里都是一团浆糊。