【刷题】 leetcode 2 .两数相加

在这里插入图片描述

两数相加

两数相加
- 1 思路一（暴毙版）
- 2 思路二（本质出发）
谢谢阅读Thanks♪(･ω･)ﾉ
下一篇文章见！！！！！！

两数相加

我们来看看题目，，，，

往往困难的题只需要简单的叙述。

好像只用找到两个数，整合成一个链表就可以。应该

在这里插入图片描述

1 思路一（暴毙版）

首先我最快想到思路是分别根据两个链表求出对应数
然后加一起，得到和
再把和拆分储存到链表里

为此我们需要手撕一下链表头插。

 typedef struct ListNode SLTNode;SLTNode* buynode(int n) {	//开辟空间    SLTNode* node = (SLTNode*)malloc(sizeof(SLTNode));    node->next = NULL;    node->val = n;    return node;}void pushback(SLTNode** ret, int n) {	//创建节点    SLTNode* node = buynode(n);    //如果头为空 node成为头    if (*ret == NULL)    {        *ret = node;        return;    }	//找尾    SLTNode* cur = *ret;    while(cur->next) {        cur = cur->next;    }    //插入    cur->next = node;    return;}SLTNode* addTwoNumbers(SLTNode* l1, SLTNode* l2) {    //选择long long 来储存较大数    long long  num1 = 0, num2 = 0;    long long   a = 1;    //计算数一    while (l1 != NULL) {        num1 += (l1->val) * a;        l1 = l1->next;        a *= 10;    }    a = 1;    //计算数二    while (l2 != NULL) {        num2 += (l2->val) * a;        l2 = l2->next;        a *= 10;    }    //求和    long long  sum = num1 + num2;    //构建链表    SLTNode* ret = NULL;    if(sum == 0)    {        pushback(&ret,0);        return ret;    }    while (sum != 0) {        long long  n = sum % 10;        pushback(&ret, n);        sum = sum / 10;    }    //返回链表    return ret;}

一顿操作猛如虎，一看提交原地杵········

在这里插入图片描述

虽然我已经使用最大的数据类型 long long ,但是最后的测试数据太大了，还有3 个样例无法通过。这下子要从头开始了。

（这就得夸夸力扣了，丰富的测试用例，不会随便让你过）

2 思路二（本质出发）

思路一的简单加和不能完成目的，那我们只好深入到加法的本质中去：

按位计算，满10进一 ,逐个逐个计算

这样就算把天文数字填进来，只要内存够，咱都能解决!!!

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
typedef struct ListNode Listnode;
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    //创建头结点
    Listnode* head = (Listnode*)malloc(sizeof(Listnode));
    //创建尾指针
    Listnode* cur = head;
    //进位数
    int t = 0;
    //l1 l2 t 全为空才停止
    while(l1||l2||t){
        //l1 为真则把值赋值在t上
        if(l1) {
            t += l1->val;
            l1 = l1->next;
        }
        //l2 为真则把值赋值在t上
        if(l2) {
            t += l2->val;
            l2 = l2->next;
        }
        //创建节点
        cur->next = ( Listnode *)malloc(sizeof(Listnode));
        cur->next->val = t % 10;
        cur->next->next = NULL;
        //向后移动
        cur = cur->next;
        t /= 10;
    }
    return head->next;

}

一气呵成，呼~~~~

我们舍去手撕链表头插的痛苦。直接改为“满足条件”就开辟新空间。因此为了方便这里使用带头链表。

提交！过过过过啦！！！！！！

在这里插入图片描述