这题拿到手上，我一直在考虑一个问题就是，能不能通过不预先遍历的方法去做。
呜呜，原谅我的无知，我想不出来。
那就只能先遍历一遍了，反正也是很不影响时间。
一看到这题，就冒出了两种解题方法，第一种是预先通过两个数组把两个链表中的数据保存下来，然后就变成了大数加法了,然后再把结果放到一个新的链表中。
还一种是补充短的链表，然后进行各个位相加，最后考虑进位。等等，好像不可以吧，如果这样的话，进位没办法解决了，毕竟是一个单链表。如果可行，最后还是要借助数组完成进位。
两种方法我都试一下吧！！！
解法1：开始我想着顺着存，这样就可以在统计长度的时候把数据放入数组中.最后发现进位难处理
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ int *arr1 = new int[1000002]; //用来保存结果 int *arr2 = new int[1000002]; ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here //末尾对齐,遍历一遍 int len1 = 0; int len2 = 0; ListNode *p1 = head1; ListNode *p2 = head2; while(p1 != nullptr) { p1 = p1->next; len1++; } while(p2 != nullptr) { p2 = p2->next; len2++; } //将各个数位保存到数组中 p1 = head1; for(int i=len1-1;i>=0;--i) { arr1[i] = p1->val; p1 = p1->next; } p2 = head2; for(int i=len2-1;i>=0;--i) { arr2[i] = p2->val; p2 = p2->next; } //各个位相加 int len = len1 > len2 ? len1:len2; for(int i=0;i<len;++i) { arr1[i] = arr1[i] + arr2[i]; arr1[i+1] = arr1[i+1] + arr1[i]/10; arr1[i] = arr1[i]%10; } ListNode *ans = nullptr; ListNode *p = nullptr; if(arr1[len] > 0) { ListNode *s = new ListNode(arr1[len]); s->next = nullptr; ans = s; p = s; } for(int k=len-1;k>=0;k--) { ListNode *s = new ListNode(arr1[k]); s->next = nullptr; if(ans == nullptr) { ans = s; p = s; } else { p->next = s; p = p->next; } } return ans; } };
这里好像忘记释放数组里的内存了，一个好的习惯，还是建议释放掉
解法2：
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: /** * * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here //末尾对齐,遍历一遍 int len1 = 0; int len2 = 0; ListNode *p1 = head1; ListNode *p2 = head2; while(p1 != nullptr) { p1 = p1->next; len1++; } while(p2 != nullptr) { p2 = p2->next; len2++; } if(len1 > len2) { for(int i=0;i<len1-len2;++i) { ListNode *s = new ListNode(0); s->next = head2; head2 = s; } } if(len2 > len1) { for(int i=0;i<len2-len1;++i) { ListNode *s = new ListNode(0); s->next = head1; head1 = s; } } p1 = head1; p2 = head2; while(p1 != nullptr) { p1->val = p1->val + p2->val; p1 = p1->next; p2 = p2->next; } int len = len1 > len2 ? len1:len2; int *arr = new int[len+2]; p1 = head1; for(int i=len-1;i>=0;--i) { arr[i] = p1->val; // arr[i+1] = arr[i+1] + arr[i]/10; // arr[i] = arr[i]%10; p1 = p1->next; } for(int i=0;i<len;++i) { arr[i+1] = arr[i+1] + arr[i]/10; arr[i] = arr[i]%10; } ListNode *ans = nullptr; ListNode *p = nullptr; if(arr[len] > 0) { ListNode *s = new ListNode(arr[len]); s->next = nullptr; ans = s; p = s; } for(int k=len-1;k>=0;--k) { ListNode *s = new ListNode(arr[k]); s->next = nullptr; if(ans == nullptr) { ans = s; p = s; } else { p->next = s; p = p->next; } } delete []arr; return ans; } };
