【优选算法专栏】专题九：链表--------两数之和-Toy模板网

这篇具有很好参考价值的文章主要介绍了【优选算法专栏】专题九：链表--------两数之和。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

本专栏内容为：算法学习专栏，分为优选算法专栏，贪心算法专栏，动态规划专栏以及递归，搜索与回溯算法专栏四部分。通过本专栏的深入学习，你可以了解并掌握算法。

💓博主csdn个人主页：小小unicorn
⏩专栏分类：算法从入门到精通
🚚代码仓库：小小unicorn的代码仓库🚚
🌹🌹🌹关注我带你学习编程知识

题目来源

本题来源为：

Leetcode2.两数之和

题目描述：

给你两个非空的链表，表示两个非负的整数。它们每位数字都是按照逆序的方式存储的，并且每个节点只能存储一位数字。

请你将两个数相加，并以相同形式返回一个表示和的链表。

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
【优选算法专栏】专题九：链表--------两数之和,# 优选算法专栏,算法专栏,算法,链表,数据结构

题目解析

分析题目：就是两个数相加的过程，只是换成了在链表中进行加减操作。
例如下面这个例子：
【优选算法专栏】专题九：链表--------两数之和,# 优选算法专栏,算法专栏,算法,链表,数据结构
注意：因为传的是逆序。而加法操作正好是从低位开始，所以逆序会方便我们的操作。最后要将结果变成逆序输出即可。

算法原理

本题的算法原理很简单，其实就是模拟一下两数相加的过程。

首先为了方便，我们先定义一个虚拟头节点。
其次定义两个指针分别指向两个链表的头节点，定义一个新的变量t来进行一个进位操作，然后模拟两数相加的过程。

【优选算法专栏】专题九：链表--------两数之和,# 优选算法专栏,算法专栏,算法,链表,数据结构
注意：计算结果保存在t变量中，是将这个结果的个位放在链表中。文章来源地址https://www.toymoban.com/news/detail-834381.html

代码实现

/**
 * 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*cur1=l1;
        ListNode*cur2=l2;
        //创建一个虚拟头节点，记录最终结果
        ListNode*newnode =new ListNode(0);
        ListNode*prev=newnode;//尾指针
        int t=0;//记录进位

        while(cur1||cur2||t)
        {
            //先加第一个链表
            if(cur1)
            {
                t+=cur1->val;
                cur1=cur1->next;
            }
            //加上第二个来链表
            if(cur2)
            {
                t+=cur2->val;
                cur2=cur2->next;
            }
            //将各位保存在链表中
            prev->next=new ListNode(t%10);
            prev=prev->next;
            t/=10;
        }
        prev=newnode->next;
        delete  newnode;
        return prev;
    }
};