Add-Two-Numbers问题描述
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
想法与实现
失败的尝试
最开始，因为看错了题目，以为是按照正常的顺序存储的，就是说我认为2->4->3代表的数字是243，其实并不是，而是342。因为错误的理解，所以最开始我的做法是先把链表转为int，然后再将得到的int转为链表。代码如下~
// wrong!! becauce the result overflows
ListNode *addTwoNumbersErr(ListNode *l1, ListNode *l2) {
int leftVal = 0, rightVal = 0;
// calculate the value that l1 represents
int digit = 1;
while (l1 != NULL)
{
leftVal = leftVal + l1->val * digit;
digit = digit * 10;
l1 = l1->next;
}
// calculate the value that l2 represents
digit = 1;
while (l2 != NULL)
{
rightVal = rightVal + l2->val * digit;
digit = digit * 10;
l2 = l2->next;
}
// calculate the result
int result = leftVal + rightVal;
// calculate the numbers of the digits
int mod = 1;
while (result % power(mod) != result)
{
mod++;
}
ListNode *answer = NULL;
ListNode *pointer;
// construct the answer list
for (int i = 1; i <= mod; i++)
{
int mypower = power(i);
int bit = result % 10;
result = result / 10;
ListNode *buf = new ListNode(bit);
if (answer == NULL)
{
answer = buf;
pointer = answer;
}
else
{
pointer->next = buf;
pointer = buf;
}
}
return answer;
}
int power(int n)
{
int result = 1;
for (int i = 0; i < n; i++)
result *= 10;
return result;
}
一共1555个测试用例，这样的写法卡在了第350个左右，原因是，result变量溢出了。测试用例为
Input: {9}, {1,9,9,9,9,9,9,9,9,9}
Output: {8,0,4,5,6,0,0,1,4,1,0,0,0,0,0}
Expected: {0,0,0,0,0,0,0,0,0,0,1}
因为发现这样的写法是费力不讨好，于是决定重新写，不把l1，l2转为int然后加起来，而是逐位加法，这样最大的数字不过18，不会出现溢出的情况。
逐位加法
因为链表中前面的是低位，因此很适合直接按照手算加法的步骤去解决这个问题，逐位相加，大于10就进位，这样。代码实现如下~
ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {
ListNode *answer = NULL;
ListNode *pointer;
/*0: <10; 1: >=10*/
int flag = 0;
// deal with l1 bit and l2 bit
while (l1 != NULL && l2 != NULL)
{
if (l1->val + l2->val + flag < 10)
{
if (answer == NULL)
{
answer = new ListNode(l1->val + l2->val + flag);
pointer = answer;
flag = 0;
}
else
{
ListNode *buf = new ListNode(l1->val + l2->val + flag);
pointer->next = buf;
pointer = buf;
flag = 0;
}
}
else
{
if (answer == NULL)
{
answer = new ListNode(l1->val + l2->val + flag - 10);
pointer = answer;
flag = 1;
}
else
{
ListNode *buf = new ListNode(l1->val + l2->val + flag - 10);
pointer->next = buf;
pointer = buf;
flag = 1;
}
}
l1 = l1->next;
l2 = l2->next;
}
// now l1 is NULL or l2 is NULL
if (l1 != NULL)
{
while (l1 != NULL)
{
// flag is 0, so the next bits are the rest
if (flag == 0)
{
pointer->next = l1;
break;
}
// deal with the situation that flag is 1
else
{
if (l1->val + flag < 10)
{
ListNode *buf = new ListNode(l1->val + flag);
pointer->next = buf;
pointer = buf;
flag = 0;
}
else
{
ListNode *buf = new ListNode(l1->val + flag - 10);
pointer->next = buf;
pointer = buf;
flag = 1;
}
}
l1 = l1->next;
}
}
else if (l2 != NULL)
{
while (l2 != NULL)
{
if (flag == 0)
{
pointer->next = l2;
break;
}
else
{
if (l2->val + flag < 10)
{
ListNode *buf = new ListNode(l2->val + flag);
pointer->next = buf;
pointer = buf;
flag = 0;
}
else
{
ListNode *buf = new ListNode(l2->val + flag - 10);
pointer->next = buf;
pointer = buf;
flag = 1;
}
}
l2 = l2->next;
}
}
// l1 and l2 are all NULL, but if flag is 1, need a new bit
if (flag == 1)
{
pointer->next = new ListNode(1);
}
return answer;
}
很多重复代码，都是按照人类计算加法的方式一步步来的。没什么技巧在里面，完全是数学知识。虽然代码很长，不过就时间复杂度而言应该是O(MAX(l1, l2))吧，最多只需要l1，l2中最大长度次循环就够了。
总结
这个题目完全是数学知识，细心就好。我觉得时间复杂度最好也就是O(MAX(l1, l2))了吧，因为无论如何都至少需要遍历l1和l2一遍。不过上面的代码还是有很多地方可以继续做一些小小的优化的。