题目

给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

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

解题思路

本道题目考察的知识点：

1. 链表的创建和插入；
2. 对溢出情况的考虑；

我的解答

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
    struct ListNode *p = l1;
    struct ListNode *q = l2;
    struct ListNode *head = NULL;
    struct ListNode *L3 = NULL;
    struct ListNode *dummyHead = NULL;
    
    int carry = 0;
    int sum = 0;
    
    while(p != NULL || q != NULL)
    {
        
        int x = (p != NULL) ? p->val : 0;
        int y = (q != NULL) ? q->val : 0;
        
        sum = carry + x + y;
        
        dummyHead = malloc(sizeof(struct ListNode));
        dummyHead->val = sum % 10;
        dummyHead->next = NULL;
        
        printf("%d\n", dummyHead->val);
        /* 插入节点 */
        if (NULL == head)
            head = dummyHead;
        else
            L3->next = dummyHead;

        L3 = dummyHead;
        
        carry = (sum < 10) ? 0 : 1;
        
        if (p != NULL)
            p = p->next;
        
        if (q != NULL)
            q = q->next;
    }
    
    /* 针对溢出的特殊处理 */
    if (1 == carry)
    {
        dummyHead = malloc(sizeof(struct ListNode));
        dummyHead->val = 1;
        dummyHead->next = NULL;
        L3->next = dummyHead;
    }
        
    return head;
}

示意图

链表的新建和插入.png