LeetCode：2.两数相加

本文介绍: 链表表示很大数字的两数相加，过程易想，情况不多，但多思考能很大程度减轻代码量，C语言实现：代码+注释，

题目：编辑2. 两数相加 – 力扣（LeetCode）

2. 两数相加 – 力扣（LeetCode）

题目：2. 两数相加 – 力扣（LeetCode）

分析问题：

本题目前来看，只能老老实实的做，仅有这一种做法：

1，首先排除，把每一个结点的val抠出来，再添回去的做法，这样复杂度会多很多，而且，链表的结点不可能太少，来个1000，你根本没法表示，

2，那么一来，很容易想到，分结点加，加好后放入新开辟的链表结点里，易想到有两种情况，加出超过10，和每超出10，而关于两个链表的长度不一致的做法，博主是分情况的，使代码复杂了，

而官方题解的解法很巧妙的避开了这个问题。

官方的优秀代码+博主的注释：

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *head = NULL, *tail = NULL;
    int carry = 0;
    while (l1 || l2) {
        int n1 = l1 ? l1->val : 0;//当l1为NULL的时候视作val == 0
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + carry;
        if (!head) {//解决单链表第一个结点不好扔循环的问题，
                //博主不喜欢这种操作，除了第一次，这个无用的判断走了很多轮
            head = tail = malloc(sizeof(struct ListNode));
            tail->val = sum % 10;
            tail->next = NULL;
        } else {
            tail->next = malloc(sizeof(struct ListNode));//持续创建新链表的结点和赋值
            tail->next->val = sum % 10;
            tail = tail->next;
            tail->next = NULL;
        }
        carry = sum / 10;
        if (l1) {//遍历
            l1 = l1->next;
        }
        if (l2) {
            l2 = l2->next;
        }
    }
    if (carry > 0) {//最后检验会不会多出一个结点，例子：200+900 == 1100，三位进四位
        tail->next = malloc(sizeof(struct ListNode));
        tail->next->val = carry;
        tail->next->next = NULL;
    }
    return head;
}

作者：力扣官方题解
链接：https://leetcode.cn/problems/add-two-numbers/solutions/435246/liang-shu-xiang-jia-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

博主的辣眼代码，无注释，拉出来拷打自己：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* BuyNode()
{
    struct ListNode* ps = (struct ListNode*)malloc(sizeof(struct ListNode));
    if(ps != NULL){
        ps->next = NULL;
        return ps;
    }
    else{
        return NULL;
    }
}
void CopyOther(struct ListNode* ps, struct ListNode* pcur)
{
    while(ps != NULL){
        pcur->next = BuyNode();
        pcur = pcur->next;;
        pcur->val = ps->val;
        ps = ps->next;
    }
    return;
}

void Case3(struct ListNode* ps,struct ListNode* pcur)
{
    while(ps != NULL){
        if(ps->val + 1 >= 10){
            pcur->next = BuyNode();
            pcur = pcur->next;
            pcur->val = ps->val + 1 - 10;
            ps = ps->next;
        }
        else{
            pcur->next = BuyNode();
            pcur = pcur->next;
            pcur->val = ps->val + 1;
            ps = ps->next;
            CopyOther(ps, pcur);
            return;
        }
    }
    pcur->next = BuyNode();
    pcur = pcur->next;
    pcur->val = 1;
    return;
}
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode* p1 = l1,*p2 = l2;
    struct ListNode* pReturn = BuyNode(), *pcur = pReturn;//pReturn 哨兵结点
    int tmp = 0;//进一
    while(p1 && p2){
        if(tmp + p1->val + p2->val >= 10){
            pcur->next = BuyNode();
            pcur->next->val = (tmp + p1->val + p2->val) - 10;
            pcur = pcur->next;
            tmp = 1;
            p1 = p1->next;
            p2 = p2->next;

        }
        else{
            pcur->next = BuyNode();
            pcur->next->val = tmp + p1->val + p2->val;
            pcur = pcur->next;
            tmp = 0;
            p1 = p1->next;
            p2 = p2->next;
        }
    }
    if(tmp){
        if(p1 == NULL){
            Case3(p2, pcur);
            return pReturn->next;
        }
        else{
            Case3(p1, pcur);
            return pReturn->next;
        
        }
    }
    if(p1 == NULL){
        CopyOther(p2, pcur);
        return pReturn->next;
        
    }
    else{
        CopyOther(p1, pcur);
        return pReturn->next;

    }
}