【力扣专题栏】两数相加，如何实现存储在链表中的整数相加？

题解目录

• 1、题目描述+解释
• • 2、算法原理解析
  • • 3、代码编写（原始版本）
    • 4、代码编写（优化版本）

1、题目描述+解释

2、算法原理解析

3、代码编写（原始版本）

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
    	//创建新链表，有头结点的。
        ListNode* new_head=new ListNode(0);
        ListNode* ptail=new ListNode(0);
        //使用两个指针分别指向两个链表的头结点
        ListNode* cur1=l1;
        ListNode* cur2=l2;
        int t=0;//记录相加后的数字
        int num=0;//记录个位；
        while(cur1&&cur2)
        {
            t=t+cur1->val+cur2->val;
            //取出个位
            num=t%10;
            //插入到新节点后面
            if(new_head->next==nullptr)
            {
                ListNode* newNode=new ListNode(num);
                new_head->next=newNode;
                ptail=newNode;
            }
            else
            {
                ListNode* newNode=new ListNode(num);
                ptail->next=newNode;
                ptail=newNode;
            }
            t/=10;
            cur1=cur1->next;
            cur2=cur2->next;
        }
        //判断是哪个先走完
        if(cur1==nullptr)
        {
            //把cur2的后面加入
            while(cur2)
            {
                t=t+cur2->val;
                num=t%10;
                ListNode* newNode=new ListNode(num);
                ptail->next=newNode;
                ptail=newNode;
                t/=10;
                cur2=cur2->next;
            }
        }
        if(cur2==nullptr)
        {
            //把cur1的后面加入
            while(cur1)
            {
                t=t+cur1->val;
                num=t%10;
                ListNode* newNode=new ListNode(num);
                ptail->next=newNode;
                ptail=newNode;
                t/=10;
                cur1=cur1->next;
            }
        }
        //判断t是否为0
        if(t)
        {
            ListNode* newNode=new ListNode(t);
            ptail->next=newNode;
            ptail=newNode;
        }
        return new_head->next;
    }
};

4、代码编写（优化版本）

/**
 * 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* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* NewHead=new ListNode(0);
        ListNode* Ptail=NewHead;
        ListNode* cur1=l1;
        ListNode* cur2=l2;
        int t=0;
        while(cur1||cur2||t)//都为假，才跳出循环
        {
            if(cur1)
            {
                t+=cur1->val;
                cur1=cur1->next;
            }
            if(cur2)
            {
                t+=cur2->val;
                cur2=cur2->next;
            }
            Ptail->next=new ListNode(t%10);
            Ptail=Ptail->next;
            t/=10;
        }
        //释放资源
        Ptail=NewHead->next;
        delete NewHead;

        return Ptail;
    }
};