`
SunnyYoona
  • 浏览: 361505 次
社区版块
存档分类
最新评论

[LeetCode]2.Add Two Numbers

 
阅读更多

【题目】

You are given two linked lists representing two non-negative numbers. 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.

Input:(2 -> 4 -> 3) + (5 -> 6 -> 4)
Output:7 -> 0 -> 8

【题意】

给你两个链表,表示两个非负整数。数字在链表中按反序存储,例如342在链表中为2->4->3。链表每一个节点包含一个数字(0-9)。

计算这两个数字和并以链表形式返回。

【分析】

【代码1】

/*********************************
*   日期:2014-01-27
*   作者:SJF0115
*   题目: 2.Add Two Numbers
*   网址:http://oj.leetcode.com/problems/add-two-numbers/
*   结果:AC
*   来源:LeetCode
*   总结:
**********************************/
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;

struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *head = (ListNode *)malloc(sizeof(ListNode));
        ListNode *pre = head;
        ListNode *node = NULL;
        //进位
        int c = 0,sum;
        //加法
        while(l1 != NULL && l2 != NULL){
            sum = l1->val + l2->val + c;
            c = sum / 10;
            node = (ListNode *)malloc(sizeof(ListNode));
            node->val = sum % 10;
            node->next = NULL;
            //尾插法
            pre->next = node;
            pre = node;
            l1 = l1->next;
            l2 = l2->next;
        }
        //例如:2->4->3->1   5->6->4
        while(l1 != NULL){
            sum = l1->val + c;
            c = sum / 10;
            node = (ListNode *)malloc(sizeof(ListNode));
            node->val = sum % 10;
            node->next = NULL;
            //尾插法
            pre->next = node;
            pre = node;
            l1 = l1->next;
        }
        //例如:2->4->3   5->6->4->1
        while(l2 != NULL){
            sum = l2->val + c;
            c = sum / 10;
            node = (ListNode *)malloc(sizeof(ListNode));
            node->val = sum % 10;
            node->next = NULL;
            //尾插法
            pre->next = node;
            pre = node;
            l2 = l2->next;
        }
        //最后一位还有进位
        if(c > 0){
            node = (ListNode *)malloc(sizeof(ListNode));
            node->val = c;
            node->next = NULL;
            //尾插法
            pre->next = node;
            pre = node;
        }
        return head->next;
    }
};
int main() {
    Solution solution;
    int A[] = {2,4,7,9};
    int B[] = {5,6,4};
    ListNode *head = NULL;
    ListNode *head1 = (ListNode*)malloc(sizeof(ListNode));
    ListNode *head2 = (ListNode*)malloc(sizeof(ListNode));
    head1->next = NULL;
    head2->next = NULL;
    ListNode *node;
    ListNode *pre = head1;
    for(int i = 0;i < 4;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = A[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    pre = head2;
    for(int i = 0;i < 3;i++){
        node = (ListNode*)malloc(sizeof(ListNode));
        node->val = B[i];
        node->next = NULL;
        pre->next = node;
        pre = node;
    }
    head = solution.addTwoNumbers(head1->next,head2->next);
    while(head != NULL){
        printf("%d ",head->val);
        head = head->next;
    }
    return 0;
}


【代码2】

class Solution {
public:
    ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
        ListNode *head = (ListNode *)malloc(sizeof(ListNode));
        ListNode *pre = head;
        ListNode *node = NULL;
        //进位
        int c = 0,sum,val1,val2;
        //加法
        while(l1 != NULL || l2 != NULL || c != 0){
            val1 = (l1 == NULL ? 0 : l1->val);
            val2 = (l2 == NULL ? 0 : l2->val);
            sum = val1 + val2 + c;
            c = sum / 10;
            node = (ListNode *)malloc(sizeof(ListNode));
            node->val = sum % 10;
            node->next = NULL;
            //尾插法
            pre->next = node;
            pre = node;
            l1 = (l1 == NULL ? NULL : l1->next);
            l2 = (l2 == NULL ? NULL : l2->next);
        }
        return head->next;
    }
};


分享到:
评论

相关推荐

    LeetCode2 Add Two Numbers

    You are given two non-empty linked lists ... 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. java AC版本

    leetcode卡-LeetCode:我的LeetCode解决方案

    2. Add Two Numbers], Linked list 2017.06.13 打卡[LeetCode 200. Number of Islands], BFS 2017.06.14 打卡[LeetCode 3. Longest Substring Without Repeating Characters], N/A 2017.06.15 打卡[LeetCode 407. ...

    程序员面试宝典LeetCode刷题手册

    2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 7. Reverse Integer 9. Palindrome Number 11. Container With Most Water 13. Roman to Integer 15. 3Sum ...

    leetcode add two numbers

    自己写的一个完整的程序,包括main函数,在VS上面提交通过,但是放到leetcode上面会出现问题;只是作为一个参考,一起学习学习0.o!解决的问题有:第一:两个链表的最后一个值相加后进位的问题;第二:两个链表的...

    AddTwoNumbers.java

    leetcode:Add Two Numbers(java)

    lrucacheleetcode-leetcode:leetcode

    2. Add Two Numbers 3. Longest Substring Without Repeating Characters 4. Median of Two Sorted Arrays 5. Longest Palindromic Substring 7. Reverse Integer 9. Palindrome Number 11. Container With Most ...

    python-leetcode面试题解之两数相加AddTwoNumbers.zip

    python python_leetcode面试题解之两数相加AddTwoNumbers

    leetcode2sumc-leetcode:leetcode.com的解决方案

    leetcode_002_add_two_numbers_test.c .... 添加 -b 以运行基准测试(显示 2 秒内运行了多少次)。 例如,使用基准运行 leetcode_001_two_sum_test.c 有 5 个断言 sh test.sh 001 -b ..... Benchmark: 225 runs in 2...

    LeetCode 1.Two Sum

    Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same ...

    add-two-numbers

    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. Input: (2 -&gt; 4 -&gt; 3) + (5 -&gt; 6 -&gt; 4) Output: 7 -&gt; 0 ...

    addTwoNumbers_leetcode_

    给你两个?非空 的链表,表示两个非负的整数。它们每位数字都是按照?逆序?的方式存储的,并且每个节点只能存储?一位?数字。请你将两个数相加,并以相同形式返回一个表示和的链表。你可以假设除了数字 0 之外,这两个...

    LeetCode最全代码

    421 | [Maximum XOR of Two Numbers in an Array](https://leetcode.com/problems/maximum-xor-of-two-numbers-in-an-array/) | [C++](./C++/maximum-xor-of-two-numbers-in-an-array.cpp) [Python](./Python/...

    Two Sum leetcode c++

    The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2)...

    leetcode2sumc-2021-LeetCode-02_Add_Two_Numbers:2021-LeetCode-02_Add_Two

    leetcode 2 和 c 2021-LeetCode-02_Add_...addTwoNumbers(_ l1: ListNode?, _ l2: ListNode?) -&gt; ListNode? { guard l1 != nil && l2 != nil else { return nil } var resultTail = ListNode() let resultHead = resu

    leetcode所有报错-leetcode:leetcode

    2.Code::Blocks报错,leetcode服务器通过,未知原因 3.leetcode要求函数返回数组用malloc,例int* ret = malloc(sizeof(int) * 2); 2. Add Two Numbers struct复习 可以在定义结构体的同时定义结构体变量: struct ...

    手绘算法力扣 2 两数相加(Add Two Numbers)

    手绘算法力扣 2 两数相加(Add Two Numbers)

    leetcode添加元素使和等于-LeetcodePractice:力码练习

    leetcode添加元素使和等于 LeetcodePractice 用C++刷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 ...

    leetcode题库-algorithm_exercise:算法练习

    leetcode题库 algorithm ...org.jxch.study.algorithm.exercise.leetcode.alibaba.AddTwoNumbers org.jxch.study.algorithm.exercise.leetcode.alibaba.LongestSubstringWithoutRepeatingCharacters

    leetcode2sumc-add-two-numbers-solution:我的LeetCodeC解决方案:添加两个数字

    Add the two numbers and return the sum as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Example 1: Input: l1 = [2,4,3], l2 = [5,6,4] Output...

    leetcode338-LeetCode:LeetCode刷题总结

    2.Add Two Numbers 3.Longest Substring Without Repeating Characters 4.Median of Two Sorted Arrays 5.Longest Palindromic Substring (Manacher算法待完成) 6.ZigZag Conversion 7.Reverse Integer 8.String to ...

Global site tag (gtag.js) - Google Analytics