《LeetCode 热题 HOT 100》—— 两数相加

简介: 《LeetCode 热题 HOT 100》—— 两数相加

首先,这道题整体还是比较简单的,只要把握题意,仔细思考,我相信各位小伙伴都可以战胜它!

首先,我们还是先阅读题目:

 

 

输入:l1 = [2,4,3], l2 = [5,6,4]

输出:[7,0,8]

解释:342 + 465 = 807.

示例 2:

输入:l1 = [0], l2 = [0]

输出:[0]

示例 3:

输入:l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]

输出:[8,9,9,9,0,0,0,1]


💥题意分析:

首先,此函数接收两个链表 l1 和 l2,并返回一个新的链表,该链表表示两个输入列表的总和。大概的题意就是这样。接下来,我们具体分析。


💨 解题思路:

本题整体上的思想即为:使用初等数学的方法,采用逐位累加的策略对其进行操作。

  1. 要添加链表表示的两个数字,我们可以同时遍历两个链表并添加相应的节点。
  2. 首先我们先设置一个 哨兵位结点 用于跟踪新列表的头部,newHead 用于遍历新列表。carry 进位变量表示 进位标识符。
  3. 我们可以跟踪进位并将其添加到下一个节点的总和中。如果总和大于 9,我们需要将 1 转移到下一个节点。
  4. 其次,如果两个链表的长度不等,此时将我们需要进行补位操作,即较短的链表在末尾补零使得两个连表长度相等,再逐个元素对其相加

图解如下:

  • 第一步:

  • 第二步:

  • 第三步:

 

 

代码如下:

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode* dummy = new ListNode(-1);  //设置哨兵位结点
    ListNode* newHead = dummy;           //用于遍历新的链表所用
    int carry = 0;                       //进位标识符
    while (l1 || l2 || carry) {          //循环将继续,直到输入列表和进位值都为空
        int n = l1 ? l1->val: 0;
        int m = l2 ? l2->val: 0;
        int sum =  n+ m + carry; 
    //在每次迭代中,我们添加当前节点的值和进位值
        carry = sum / 10;
    //创建一个数值为【sum % 10】的新节点,并将其设置当前结点的下一个结点
        newHead->next = new ListNode(sum % 10);        
        newHead = newHead->next;         //更新当前节点的位置
        
     //往后进行迭代操作
       l1 = l1 ? l1->next : NULL;  
       l2 = l2 ? l2->next : NULL;
    }
    return dummy->next;  //最后,我们返回哨兵位节点的下一个节点,即新列表的头部。
    }
};

到此,本题便讲解结束!!!

相关文章
|
15天前
LeetCode 热题100——单调栈
LeetCode 热题100——单调栈
21 0
|
15天前
|
存储
LeetCode热题 首题 两数之和
LeetCode热题 首题 两数之和
21 1
|
15天前
|
存储 算法
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
《LeetCode 热题 HOT 100》——寻找两个正序数组的中位数
|
15天前
|
网络协议
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
《 LeetCode 热题 HOT 100》——无重复字符的最长子串
|
15天前
leetcode热题100. 字母异位词分组
leetcode热题100. 字母异位词分组
20 0
|
15天前
leetcode热题100.二叉树中的最大路径和
leetcode热题100.二叉树中的最大路径和
20 0
|
15天前
|
算法
leetcode热题100.三数之和
leetcode热题100.三数之和
20 1
|
15天前
leetcode热题100. 二叉树的最近公共祖先
leetcode热题100. 二叉树的最近公共祖先
26 0
|
15天前
|
vr&ar
leetcode热题100.路径总和 III
leetcode热题100.路径总和 III
20 1
|
15天前
|
机器学习/深度学习 算法 索引
leetcode热题100.两数之和
leetcode热题100.两数之和
17 1