描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 O(n)，时间复杂度 O(n)
例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。
示例1：
输入：[9,3,7],[6,3]
返回值：{1,0,0,0}
说明：如题面解释示例2：
输入：[0],[6,3]
返回值：{6,3}
解题思路：
其实，看到这个题目，首先想到的是将链表逐个逐个取出，组成一个数字，然后通过数字相加得到最终的结果，然后再把结果的每一位数字分别填入新的链表中。
但是，想法是好的，现实是残酷的！
题中要求链表长度的范围为0 ~ ，即如果将它组成一个数字，那得要100万位的数字，显然不现实，只能回归到链表的操作上来。
题目要求时间复杂度为O(n)，那只要顺序轮询就可以了。因为是按位加法，还要考虑到进位。类似如下的方式：
所以，首先想到的就是将链表翻转，然后从头计算。
代码：
struct ListNode* ReverseList(struct ListNode* pHead );
struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2 ) {if (head1 == NULL) { //确定链表是否有效return head2;}if (head2 == NULL) {return head1;}head1 = ReverseList(head1); //翻转链表head2 = ReverseList(head2);struct ListNode* nHead = (struct ListNode*)malloc(sizeof(struct ListNode)); //申请一个新的节点，很有用struct ListNode* p = nHead;int vForward = 0;while (head1 != NULL && head2 != NULL) { //位数对齐，先计算p->next = head1;p = p->next;p->val = vForward + head1->val + head2->val;if (p->val >= 10) {p->val -= 10;vForward = 1;} else {vForward = 0;}head1 = head1->next;head2 = head2->next;}p->next = (head1 == NULL) ? head2 : head1; //多出来的部分需要单独处理while (p->next != NULL) {p = p->next;p->val = vForward + p->val;if (p->val >= 10) {p->val -= 10;vForward = 1;} else {vForward = 0;}}if (vForward) { //可能还有进位，最开始malloc的节点就用上了p->next = nHead;nHead = nHead->next;p = p->next;p->val = 1;p->next = NULL;} else {p = nHead;nHead = nHead->next;free(p);}nHead = ReverseList(nHead); //计算完成，再来一次翻转return nHead;
}struct ListNode* ReverseList(struct ListNode* pHead ) {struct ListNode* result = NULL;for (struct ListNode* p = pHead; pHead != NULL; p = pHead) {pHead = p->next;p->next = result;result = p;}return result;
}
