问题描述

  • 给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
  • 请你将两个数相加，并以相同形式返回一个表示和的链表。
  • 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。

    示例一

    1
    2
    3
    输入：l1 = [2,4,3], l2 = [5,6,4]
    输出：[7,0,8]
    解释：342 + 465 = 807.

    示例二

    1
    2
    输入：l1 = [0], l2 = [0]
    输出：[0]

    示例三

    1
    2
    输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
    输出：[8,9,9,9,0,0,0,1]

    提示：

  • 每个链表中的节点数在范围 [1, 100] 内
  • 0 <= Node.val <= 9
  • 题目数据保证列表表示的数字不含前导零

解决思路

  • 在我认为，给了两个非空链表，然后倒序存储数字，每个节点不超过9，那么我们只需要遍历两个链表，然后初始化一个int类型的变量tag（初始值为零）来计算两个数相加超过十会进位的情况，如果链表不为空，那么数为链表中存储的数字，如果为空那么赋值为0.然后定义int类型的sum的等于两个链表的数加上tag，两年个节点一开始都为null，先判断head是否为空，如果为空那么创建一个节点使head和node都指向该节点，并且为赋值为sum%10,也就是只取和的个位数，并且给tag赋值为sum/10，也就是取了十位数。之后继续遍历直到两个链表都为空，都为空之后判断tag是否大于零，如果大于零，那么需要创建一个新的节点，并且把tag的值赋给新节点，最后返回head。

实现代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
/**
 * 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, *node = NULL;
    int tag = 0;
    while(l1 != NULL || l2 != NULL){
        int n1 = l1 ? l1->val : 0;
        int n2 = l2 ? l2->val : 0;
        int sum = n1 + n2 + tag;
        if(!head){
            head = node = malloc(sizeof(struct ListNode));
            node->val = sum % 10;
            node->next = NULL;
        }else {
            node->next = malloc(sizeof(struct ListNode));
            node->next->val = sum % 10;
            node = node->next;
            node->next = NULL;
        }
        if(l1){
            l1 = l1->next;
        }
        if(l2){
            l2 = l2->next;
        }
        tag = sum / 10;
    }
    if(tag > 0){
        node->next = malloc(sizeof(struct ListNode));
        node->next->val = tag;
        node->next->next = NULL;
    }
    return head;
}