【剑斩OFFER】算法的暴力美学——两数相加

一、题目描述

二、算法原理

思路：模拟

因为本来我们是要把链表里面的值进行翻转的，但是题目已经帮我们翻转了，所以可以直接进行加法操作就行，不过要考虑进位问题，我们使用一个值 t 来保存这个两个链表加的值，假设 t = 12 ，那么这个最终的结果是：t % 10 = 2，此时进行进位操作： t = t / 10 = 1；然后不断的进行加法运算直到：运算到第一个和第二个链表的最后值，而且当 t != 0 时，代表着加法运算还没有结束。

三、代码实现

最佳实现：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { int t = 0;//进位值 ListNode* newhead = new ListNode(0);//一个新链表的头结点，这个头结点用于返回新链表的第一个值 ListNode* cur1 = l1,*cur2 = l2; ListNode* prev = newhead;//链表的最后一个结点，用于链接加入的值 while(cur1 || cur2 || t)//只要符合其中的任意一个条件，就代表着这个链表没有结束加法运算 { if(cur1) { t += cur1->val; cur1 = cur1->next; } if(cur2) { t += cur2->val; cur2 = cur2->next; } prev->next = new ListNode(t % 10);//链接新的结点，保存该位的值 prev = prev->next;//尾结点进行更新 t = t / 10;//保存进位值 } return newhead->next; } };

代码探索：

/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* phead = new ListNode; phead->next = nullptr; ListNode* cur1 = l1,*cur2 = l2; ListNode* phead_tmp = phead; int tmp = 0; while(cur1 != nullptr && cur2 != nullptr) { tmp += cur1->val + cur2->val; ListNode* node = new ListNode; node->val = tmp % 10; node->next = nullptr; phead_tmp->next = node; phead_tmp = node; node = nullptr; tmp /= 10; cur1 = cur1 -> next; cur2 = cur2 -> next; } while(cur1 != nullptr) { tmp += cur1->val; ListNode* node = new ListNode; node->val = tmp % 10; node->next = nullptr; phead_tmp->next = node; phead_tmp = node; node = nullptr; tmp /= 10; cur1 = cur1->next; } while(cur2 != nullptr) { tmp += cur2->val; ListNode* node = new ListNode; node->val = tmp % 10; node->next = nullptr; phead_tmp->next = node; phead_tmp = node; node = nullptr; tmp /= 10; cur2 = cur2->next; } if(tmp) { ListNode* node = new ListNode; node->val = tmp; node->next = nullptr; phead_tmp->next = node; node = nullptr; } return phead->next; } };