C++实现LeetCode(2.两个数字相加)

[LeetCode] 2. Add Two Numbers 两个数字相加

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

这道并不是什么难题，算法很简单，链表的数据类型也不难，就是建立一个新链表，然后把输入的两个链表从头往后撸，每两个相加，添加一个新节点到新链表后面。为了避免两个输入链表同时为空，我们建立一个 dummy 结点，将两个结点相加生成的新结点按顺序加到 dummy 结点之后，由于 dummy 结点本身不能变，所以用一个指针 cur 来指向新链表的最后一个结点。好，可以开始让两个链表相加了，这道题好就好在最低位在链表的开头，所以可以在遍历链表的同时按从低到高的顺序直接相加。while 循环的条件两个链表中只要有一个不为空行，由于链表可能为空，所以在取当前结点值的时候，先判断一下，若为空则取0，否则取结点值。然后把两个结点值相加，同时还要加上进位 carry。然后更新 carry，直接 sum/10 即可，然后以 sum%10 为值建立一个新结点，连到 cur 后面，然后 cur 移动到下一个结点。之后再更新两个结点，若存在，则指向下一个位置。while 循环退出之后，最高位的进位问题要最后特殊处理一下，若 carry 为1，则再建一个值为1的结点，代码如下：

C++ 解法： 

class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *dummy = new ListNode(-1), *cur = dummy;
        int carry = 0;
        while (l1 || l2) {
            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;
            int sum = val1 + val2 + carry;
            carry = sum / 10;
            cur->next = new ListNode(sum % 10);
            cur = cur->next;
            if (l1) l1 = l1->next;
            if (l2) l2 = l2->next;
        }
        if (carry) cur->next = new ListNode(1);
        return dummy->next;
    }
};

Java 解法：

public class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(-1);
        ListNode cur = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int d1 = l1 == null ? 0 : l1.val;
            int d2 = l2 == null ? 0 : l2.val;
            int sum = d1 + d2 + carry;
            carry = sum >= 10 ? 1 : 0;
            cur.next = new ListNode(sum % 10);
            cur = cur.next;
            if (l1 != null) l1 = l1.next;
            if (l2 != null) l2 = l2.next;
        }
        if (carry == 1) cur.next = new ListNode(1);
        return dummy.next;
    }
}

在 CareerCup 上的这道题还有个 Follow Up，把链表存的数字方向变了，原来是表头存最低位，现在是表头存最高位，请参考另一篇文档 2.5 Add Two Numbers 两个数字相加 。

到此这篇关于C++实现LeetCode(两个数字相加)的文章就介绍到这了,更多相关C++实现两个数字相加内容请搜索我们以前的文章或继续浏览下面的相关文章希望大家以后多多支持我们！

赞 (0)

相关推荐

  • Java实现LeetCode（组合总和）

    leetcode题目 组合总和 -- leetcode 39 题目描述 给定一个无重复元素的数组 candidates 和一个目标数 target , 找出 candidates 中所有可以使数字和为 target 的组合. candidates 中的数字可以无限制重复被选取. 说明: 所有数字(包括 target)都是正整数. 解集不能包含重复的组合.  示例 1: 输入: candidates = [2,3,6,7], target = 7, 所求解集为: [   [7],   [2,2,3

  • Java实现LeetCode（报数）

    Java实现LeetCode（报数）

    题目如下: public String countAndSay(int n) { if(n == 1){ return "1"; } //递归调用,然后对字符串处理 String str = countAndSay(n-1) + "*";//为了str末尾的标记,方便循环读数 char[] c = str.toCharArray(); int count = 1; StringBuilder s = new StringBuilder(); for(int i =

  • C++实现LeetCode（三数之和）

    Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c) The solut

  • Java实现LeetCode（两数之和）

    给定一个整数数组和一个目标值,找出数组中和为目标值的两个数. 你可以假设每个输入只对应一种答案,且同样的元素不能被重复利用. 示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[1] = 2 + 7 = 9 所以返回[0, 1] 思路一:最直接的思维,两次遍历查询,时间复杂度O(N*N). 代码: public static int[] twoSum1(int[] nums, int target) { int[] label =

  • C++实现LeetCode(倒置链表)

    [LeetCode] Reverse Linked List 倒置链表 Reverse a singly linked list. Example: Input: 1->2->3->4->5->NULL Output: 5->4->3->2->1->NULL Follow up: A linked list can be reversed either iteratively or recursively. Could you implement

  • C++实现LeetCode(倒置链表之二)

    [LeetCode] 92. Reverse Linked List II 倒置链表之二 Reverse a linked list from position m to n. Do it in one-pass. Note: 1 ≤ m ≤ n ≤ length of list. Example: Input: 1->2->3->4->5->NULL, m = 2, n = 4 Output: 1->4->3->2->5->NULL 很奇怪为何

  • Java实现LeetCode（螺旋矩阵）

    LeetCode54. 螺旋矩阵 java实现 题目 难度 中 给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素. 示例 1: 输入:  [   [ 1, 2, 3 ],   [ 4, 5, 6 ],   [ 7, 8, 9 ]  ]  输出: [1,2,3,6,9,8,7,4,5] 示例 2: 输入:  [    [1, 2, 3, 4],    [5, 6, 7, 8],    [9,10,11,12]  ] 输出: [1,2,3,4,8

  • C++实现LeetCode(2.两个数字相加)

    [LeetCode] 2. Add Two Numbers 两个数字相加 You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked

  • C++实现算法两个数字相加详解

    Add Two Numbers 两个数字相加 You have two numbers represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers

  • Java C++题解leetcode消失的两个数字实例

    Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • C++实现LeetCode(170.两数之和之三 - 数据结构设计)

    [LeetCode] 170. Two Sum III - Data structure design 两数之和之三 - 数据结构设计 Design and implement a TwoSum class. It should support the following operations: add and find. add - Add the number to an internal data structure. find - Find if there exists any pai

  • C++实现LeetCode(167.两数之和之二 - 输入数组有序)

    [LeetCode] 167.Two Sum II - Input array is sorted 两数之和之二 - 输入数组有序 Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. The function twoSum should return indices of t

  • java编程实现两个大数相加代码示例

    通常情况,实现大数运算是通过BigInteger和BigDecimal两种方法.这两种方法分别表示不可变的任意精度的整数和不可变的有符号的任意精度的十进制数(浮点数).主要用于高精度计算中.这两个类使得java中的大数,高精度运算变得很简单.但本文介绍的并不是通过上述两种方法实现Java中的大数运算. 主要的思想是:把两个数存在String中了,然后将每个数字取出,放到数组,由最末位开始计算,算加法,判断是否进位,进位则前位+1,若超过长度,则copy到新的数组. 代码如下: public cl

  • C++实现LeetCode(137.单独的数字之二)

    [LeetCode] 137. Single Number II 单独的数字之二 Given a non-empty array of integers, every element appears three times except for one, which appears exactly once. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you

  • C++实现LeetCode(136.单独的数字)

    [LeetCode] 136.Single Number 单独的数字 Given a non-empty array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

  • SQL实现LeetCode(180.连续的数字)

    [LeetCode] 180.Consecutive Numbers 连续的数字 Write a SQL query to find all numbers that appear at least three times consecutively. +----+-----+ | Id | Num | +----+-----+ | 1  |  1  | | 2  |  1  | | 3  |  1  | | 4  |  2  | | 5  |  1  | | 6  |  2  | | 7  |

随机推荐