2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例 1：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[7,0,8]
解释：342 + 465 = 807.
示例 2：
输入：l1 = [0], l2 = [0]
输出：[0]
示例 3：
输入：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
题目数据保证列表表示的数字不含前导零
解题方案
参考官方题解
- C
/** * 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, *tail = NULL; int carry = 0; while (l1 || l2) { int n1 = l1 ? l1->val : 0; int n2 = l2 ? l2->val : 0; int sum = n1 + n2 + carry; if (!head) { head = tail = malloc(sizeof(struct ListNode)); tail->val = sum % 10; tail->next = NULL; } else { tail->next = malloc(sizeof(struct ListNode)); tail->next->val = sum % 10; tail = tail->next; tail->next = NULL; } carry = sum / 10; if (l1) { l1 = l1->next; } if (l2) { l2 = l2->next; } } if (carry > 0) { tail->next = malloc(sizeof(struct ListNode)); tail->next->val = carry; tail->next->next = NULL; } return head; }
445. 两数相加Ⅱ
给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外，这两个数字都不会以零开头。
示例1：
输入：l1 = [7,2,4,3], l2 = [5,6,4]
输出：[7,8,0,7]
示例2：
输入：l1 = [2,4,3], l2 = [5,6,4]
输出：[8,0,7]
示例3：
输入：l1 = [0], l2 = [0]
输出：[0]
提示：
链表的长度范围为 [1, 100]
0 <= node.val <= 9
输入数据保证链表代表的数字无前导 0进阶：如果输入链表不能翻转该如何解决？
解题方案
- C 先将链表反转再相加
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ /* 反转列表 */ struct ListNode* reverseList(struct ListNode* head) { struct ListNode* newhead = NULL; struct ListNode* curr = head; while (curr != NULL) { struct ListNode* next = curr->next; // 存储原链表第二个节点 curr->next = newhead; // 将原链表头节点添加到新链表，成为新链表头节点 newhead = curr; // 更新新链表头节点 curr = next; // 更新原链表头节点 } return newhead; } /* 两数相加 */ struct ListNode* addTwoNumbers_temp(struct ListNode* l1, struct ListNode* l2) { struct ListNode *head = NULL, *tail = NULL; int carry = 0; while (l1 || l2) { int n1 = l1 ? l1->val : 0; int n2 = l2 ? l2->val : 0; int sum = n1 + n2 + carry; if (!head) { head = tail = malloc(sizeof(struct ListNode)); tail->val = sum % 10; tail->next = NULL; } else { tail->next = malloc(sizeof(struct ListNode)); tail->next->val = sum % 10; tail = tail->next; tail->next = NULL; } carry = sum / 10; if (l1) { l1 = l1->next; } if (l2) { l2 = l2->next; } } if (carry > 0) { tail->next = malloc(sizeof(struct ListNode)); tail->next->val = carry; tail->next->next = NULL; } return head; } struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { l1 = reverseList(l1); l2 = reverseList(l2); return reverseList(addTwoNumbers_temp(l1, l2)); }
- C 使用数组，类似栈
/** * Definition for singly-linked list. * struct ListNode { * int val; * struct ListNode *next; * }; */ struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) { int l1_stack[100] = {0}, l2_stack[100] = {0}; // 定义两个数组 int l1_size = 0, l2_size = 0; // 定义两个变量，用以计算数据个数 int carry = 0; // 定义相加进位变量 struct ListNode *head = NULL, *temp = NULL; while (l1 != NULL) { l1_stack[l1_size++] = l1->val; // 将链表数据拿进数组 l1 = l1->next; } while (l2 != NULL) { l2_stack[l2_size++] = l2->val; l2 = l2->next; } while (l1_size || l2_size || carry) { int m = l1_size > 0 ? l1_stack[--l1_size] : 0; // 倒序取出数据 int n = l2_size > 0 ? l2_stack[--l2_size] : 0; int sum = m + n + carry; // 求和 carry = sum / 10; // 求进位 head = malloc(sizeof(struct ListNode)); // 申请内存 head->val = sum % 10; // 填入数据 head->next = temp; temp = head; } return head; }
