(LeetCode刷题)2. 两数相加
题目
解答一：
简单实现思路：先遍历完两个链表，把各自的数字存入两个数组，然后对应位置的数相加，若结果大于10就进位到更高位的数。
/**
* 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 = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->val = sum % 10;
tail->next = NULL;
} else {
tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next->val = sum % 10;
tail->next->next = NULL;
tail = tail->next;
}
carry = sum / 10;
if (l1) {
l1 = l1->next;
}
if (l2) {
l2 = l2->next;
}
}
if (carry > 0) {
tail->next = (struct ListNode*)malloc(sizeof(struct ListNode));
tail->next->val = carry;
tail->next->next = NULL;
}
return head;
}算法的时间复杂度就是O(N)。因为不论怎样，只要能够找到一个答案，你都必须遍历所有的数字，无法再进一步精简遍历的次数。
解答二：
不过，我们同样可以用O(N)的时间复杂度，但是可以减少代码的复杂性和提高运行的效率。我们可以使用以下策略：边遍历链表边进行加法计算并生成新的节点，然后利用一个carry变量存储进位的值，这样可以避免多次遍历和额外的存储空间。例如：
/**
* 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 || carry) {
int sum = carry;
if (l1) {
sum += l1->val;
l1 = l1->next;
}
if (l2) {
sum += l2->val;
l2 = l2->next;
}
struct ListNode *node = (struct ListNode*)malloc(sizeof(struct ListNode));
node->val = sum % 10;
node->next = NULL;
carry = sum / 10;
if (!head) {
head = node;
} else {
tail->next = node;
}
tail = node;
}
return head;
}
