两数相加

题目·要求注意点思路代码

QQ:3020889729 小蔡

题目·要求

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

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

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

示例：

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

注意点

在解答这道题目时，需要注意链表的空间和下一节点是否可查讯（非NULL）。

在创建新链表时，要记得开辟内存空间给它。在创建中间量链表时，应该及时设置next=NULL（为空时）。

思路

将两个传入链表进行迭代求和，考虑进位，然后传递值给中间链表（新创建的结果链表）。

在迭代求和时，需要注意两个链表长度是否一致——即可能出现2位数+3位数的情况，所以相加节点值时需要进行判断两个节点是否同时为空。

如果不同时为空，那么就将其中一个节点进行分配内存，并把值赋给0，以保证链表长度相同，以及按位对应的结果的计算。

在计算完所有的输入之后，我们需要对结果进行考虑——比如最有一个节点，我们应该在返回前将其next设置为NULL，保证链表查讯无误。

结果进行修正时，务必注意当前结果最有一个节点是否存在进位，如果有进位，就应该先移动到正确的最后一个节点，再设置next为NULL。

具体可参见代码中的注释 ※注释是成对出现的，※-※的代码是相关的

代码

/* * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2){ struct ListNode* temp1 = (struct ListNode*)malloc(sizeof(struct ListNode)); // 计算存储链表 struct ListNode* start = temp1; // 记录存储链表的起始地址，以便返回 temp1->next = NULL; // 务必将当前的空链表next指向NULL，否则会报错 temp1->val = 0; while(l1!=NULL || l2!=NULL) // ※当两个链表出现一长一短，如73，111，那么可以将它转换为：073，111——那么只需要检索当传入的所有已知链表都为NULL时，说明计算完毕 { temp1->val += l1->val + l2->val; // 将当前位的数值相加 if(temp1->val>=10) // 判断是否大于等于10，判断进位 { temp1->val = temp1->val - 10; temp1->next = (struct ListNode*)malloc(sizeof(struct ListNode)); // 为下一个节点分配空间 temp1->next->val = 1; // 并将下一个节点分配进位值：10~19——总是进1位且值为1 } else { temp1->val = temp1->val; temp1->next = (struct ListNode*)malloc(sizeof(struct ListNode));// 为下一个节点分配空间 temp1->next->val = 0; // 没有进位，所以下一位的值设置为0 } l1 = l1->next; // 指向下一个节点 l2 = l2->next; if(l1!=NULL || l2!=NULL) // 判断下一个节点是否全空——即不存在，如果存在一个，那么另外一个就应该被我们人为的分配空间使其存在，并将val设置为0——也就是73-073的由来 { if(l1==NULL) // 如果是l1不存在，那么就对它进行分配空间以及赋值0 { l1 = (struct ListNode*)malloc(sizeof(struct ListNode)); l1->next = NULL; l1->val = 0; } if(l2==NULL)同上 { l2 = (struct ListNode*)malloc(sizeof(struct ListNode)); l2->next = NULL; l2->val = 0; } temp1 = temp1->next; // 并且此时明显还需要计算，所以此时结果链表也需要移动到下一个节点 } if(l1 == NULL && l2 == NULL) // ※此时输入链表已经全为空——数据已经加完了。此时在退出循环前，我们要对结果链表进行一个表示修正 { // 由于此时已经计算完成，得到的结果链表也基本完整了，但是存在两种情况需要再处理一下 // ①：最后一次相加得到的结果无需进位，即小于等于9时，此时的temp1结果链表应该没有下一个节点，即此刻对应的next应该设置为NULL // ②：最有一次相加得到的结果需进位，即大于等于10时，此时的temp1结果链表是不完整的，需要继续移动到下一个节点才是完整的结果，并且在抵达最后一个节点后，同样要进行next设置为NULL的操作 if(temp1->next->val != 0) // 有进位，结果链表应该向下移动一位 { temp1 = temp1->next; temp1->next = NULL; } else // 结果链表完整，只需要将最后一个节点的next设置为NULL即可 { temp1->next = NULL; } } } return start; // 返回链表开头 }