嗯哼~
题目
描述
假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。
给定两个这种链表，请生成代表两个整数相加值的结果链表。
数据范围：0 ≤ n,m ≤ 1000000，链表任意值 0 ≤ val ≤ 9
要求：空间复杂度 O(n)，时间复杂度 O(n)
示例
思路
单链表的翻转详细讲解：反转一个单链表（<---点击可看详解）
题解代码
struct ListNode* ReverseList(struct ListNode* pHead) { // write code here struct ListNode* cur = pHead; struct ListNode* pre = NULL; while (cur != NULL) { struct ListNode* temp = cur->next; cur->next = pre; pre = cur; cur = temp; } return pre; } struct ListNode* addInList(struct ListNode* head1, struct ListNode* head2) { // write code here head1 = ReverseList(head1); head2 = ReverseList(head2); int temp = 0; int add = 0; struct ListNode* newhead = NULL; while (head1 && head2) { temp = (head1->val + head2->val + add); if (temp >= 10) { add = 1; temp %= 10; } else { add = 0; } struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode)); cur->val = temp; cur->next = newhead; newhead = cur; head1 = head1->next; head2 = head2->next; } struct ListNode* empty = head1; struct ListNode* nonempty = head2; if (head1 != NULL) { empty = head2; nonempty = head1; } while (nonempty) { temp = (nonempty->val + add); if (temp >= 10) { add = 1; temp %= 10; } else { add = 0; } struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode)); cur->val = temp; cur->next = newhead; newhead = cur; nonempty = nonempty->next; } if (add == 1) { struct ListNode* cur = (struct ListNode*)malloc(sizeof(struct ListNode)); cur->val = 1; cur->next = newhead; newhead = cur; } return newhead; }
