描述
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0 \le n,m \le 10000000≤n,m≤1000000,链表任意值 0 \le val \le 90≤val≤9
要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
假设链表中每一个节点的值都在 0 - 9 之间,那么链表整体就可以代表一个整数。
给定两个这种链表,请生成代表两个整数相加值的结果链表。
数据范围:0 \le n,m \le 10000000≤n,m≤1000000,链表任意值 0 \le val \le 90≤val≤9
要求:空间复杂度 O(n)O(n),时间复杂度 O(n)O(n)
例如:链表 1 为 9->3->7,链表 2 为 6->3,最后生成新的结果链表为 1->0->0->0。
解题思路:
最自然的做法还是三次翻转:
链表1翻转
链表2翻转
逐位求和(注意进位)
结果翻转,内存O(1),复杂度O(n)
结果翻转,内存O(1),复杂度O(n)
/** * 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* reverseList(ListNode* head){ ListNode *pre = new ListNode(0); pre->next = head; while(head->next != NULL){ ListNode *tmp = head->next; head->next = tmp->next; tmp->next = pre->next; pre->next = tmp; } return pre->next; } ListNode* addInList(ListNode* head1, ListNode* head2) { // write code here ListNode* head11 = reverseList(head1); ListNode* head12 = reverseList(head2); ListNode* res = new ListNode(-1); ListNode* cur = res; bool addOne = false; while(head11 || head12){ int num = 0; if(head11){ num += head11->val; } if(head12){ num += head12->val; } if(addOne){ num += 1; addOne = false; } if(num > 9){ addOne = true; num %= 10; } ListNode* tmp; if(head11){ head11->val = num; tmp = head11; head11 = head11->next; } if(head12){ head12->val = num; tmp = head12; head12 = head12->next; } cur->next = tmp; cur = tmp; } if(addOne){ ListNode *one = new ListNode(1); cur->next = one; cur = one; } return reverseList(res->next); } };