LeetCode-2.两数相加 使用链表加法实现

先看题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。

如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。

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

示例：

输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807

方案一：把链表转换为数字相加，再形成链表，这样做的问题是系统样例测试输入链表很长的时候，程序的基本类型存不下（溢出），这种方法不推荐。
方案二：链表的每个结点单独相加，如上面是2+5=7，6+4=10（这里要进一位）
直接上代码：

#include<stdio.h>
#include<stdlib.h>
struct ListNode {
    int val;
    struct ListNode *next;
};
/**
 * LeetCode
 * 2.两数相加
 * https://leetcode-cn.com/u/banana798/
 */
//添加结点
ListNode* add(ListNode*head, int temp){
    ListNode *p=head;
    while(1){
        if(p->next==NULL){
            p->next=(ListNode*)malloc(sizeof(ListNode));
            p->next->val = temp;
            p->next->next=NULL;
            return head;
        }
        p=p->next;
    }
}

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){
    struct ListNode *head = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *p=l1, *q=l2, *curr = head;
    //tag用以标记进位
    int tag = 0;
    while(p!=NULL||q!=NULL){
        int x = p ? p->val : 0;
        int y = q ? q->val : 0;
        int sum = tag + x + y;
        tag = sum/10;
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->next=NULL;
        curr->next->val = sum%10;
        curr=curr->next;
        if(p) p=p->next;
        if(q) q=q->next;
    }
    //最后进1位
    if(tag>0){
        curr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
        curr->next->next=NULL;
        curr->next->val = tag;
    }
    return head->next;
}

int main(){
    struct ListNode *l1 = (struct ListNode*)malloc(sizeof(struct ListNode));
    struct ListNode *l2 = (struct ListNode*)malloc(sizeof(struct ListNode));
    l1->next=NULL;
    l2->next=NULL;

    //向链表添加测试数据
    add(l1,1);
    add(l2,9);

    l1=addTwoNumbers(l1->next,l2->next);
    printf("%d->%d",l1->val,l1->next->val);
}

注意：LeetCode这里没有说明链表带不带头结点，经过我的测试后发现所有样例的链表都是没有头结点的。