题目
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例：
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
解题思路
本道题目考察的知识点：
- 链表的创建和插入；
- 对溢出情况的考虑；
我的解答
/**
* 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
