LeetCode-2.两数相加-C语言

1.两数相加

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

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

你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {

}

2.个人思路

这题考察的是链表，之前写单片机程序没用过链表。。。。又是懵逼的一题，感觉c语言白学了，得恶补数据结构的知识了。

看完链表的定义后，我的想法是，创建一个变量，然后拆分链表，第三个链表值100+第二个链表值10+头部链表，将结果保存到变量里面。

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    int a[2] ;
    int num = 10;
    struct ListNode* ret =  (struct ListNode*)malloc(3*sizeof(struct ListNode));
    ret -> next = NULL;

    a[0] += l1->val ;
    l1->next = l1->next; 

    a[0] += l1 ->val * 10;
    l1->next = l1->next; 

    a[0] += l1->val * 100;
    ret->val = a[0];
    return ret;

    ret = l2;

    a[1] += ret->val ;
    ret -> next = l2->next;

    a[1] += ret->val * 10;
    ret -> next = l2->next;

    a[1] += ret->val * 100;
    //ret -> next = l2->next;

    ret->val = a[0] + a[1];
    return ret;
}

以上是自己的，很明显遇到问题，不明白为什么l1->next = l1-> next 移动不了到下一个链表位置，l1 = l1->next也报错。一开始想使用两个for循环写的，然后数据喂想了半天处理不好，就只能一步一步来写的。又是被力扣爆扣的一题。。。。

3.正确思路

写一下加法算竖式，发现每一位相加就可以，有进位就加1。真的豁然开朗，但是指针指向下一个还未解决。

csdn之后，发现没有考虑到很多的细节。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* head = NULL;
    struct ListNode* node = NULL; 
    int sum = 0 , cnt = 0;  
    while(l1 || l2 )
    {
        int a = l1 ? l1->val : 0;
        int b = l2 ? l2->val : 0;
        sum = a + b + cnt;
        if(!head) //如果没有头链表
        {
            head = node = (struct ListNode*)malloc(sizeof(struct ListNode));  //申请一个空间，进行动态分配
            node -> val = sum % 10;
            node -> next = NULL; //将结构体 tail 的指针指向下一个节点
        }
        else
        {
            node -> next = (struct ListNode*)malloc(sizeof(struct ListNode));
            node -> next ->val = sum % 10 ; //将 sum % 10 的值赋给 tail 的下一个节点的 val 值
            node = node ->next;  //接着对 tail 初始化，使其转换成下一个节点（非常重要）
            node -> next = NULL; //对 新的 tail 的下一个节点进行初始化
        }
        cnt = sum / 10;  //这一步就是求该位上对下一位的 “ 进位值 ”
        if (l1)
            l1 = l1->next;  //对 l1 进行 “移位”，使其移动到 l1 的下一个节点
        if (l2)
            l2 = l2->next;  //对 l2 进行 “移位”，使其移动到 l2 的下一个节点
    }
    if(cnt > 0) //进行判断，如果 carry > 0，说明，该位置对下一位有进位值，需要进位
    {
        node -> next = (struct ListNode*)malloc(sizeof(struct ListNode));//申请一个空间，进行动态分配
        node -> next -> val = cnt;  //将 进位值 赋给 tail 的下一个节点
        node -> next -> next= NULL;  //对 tail 的下下个节点进行初始化
    }
    return head;
}

4.官方解析

代码如上

复杂度分析

时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

空间复杂度：O(1)。注意返回值不计入空间复杂度。

看看到一个精简版：

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* dummy = new ListNode();
        ListNode* curr = dummy;
        int carry = 0;
        while(l1 || l2 || carry) {
            int a = l1 ? l1->val : 0;
            int b = l2 ? l2->val : 0;
            int sum = a + b + carry;
            carry = sum >= 10 ? 1 : 0;
            curr->next = new ListNode(sum % 10);
            curr = curr->next;
            if(l1) l1 = l1->next;
            if(l2) l2 = l2->next;
        }
        return dummy->next;
    }