1. 原題鏈接：https://leetcode.com/problems/add-two-numbers/
2. 解題思路
- 兩個鏈表相加的解題思路比較直接
- 需要注意兩個鏈表的長度不同，有些邊界情況需要考慮周到
- 考慮進位的情況
3. 演算法
3.1 直觀演算法
- 首先，遍歷兩個鏈表長度相同的部分
- 然后，遍歷長度較長的鏈表
3.2 簡潔演算法
- 考慮將多個回圈整合到一個回圈中處理
- 首先，考慮只要其中某個鏈表還存在資料，那就繼續遍歷，由于我們不知道是哪個鏈表存在資料，因此需要在回圈內部判斷檢查一下
- 然后，考慮臨界情況：已經遍歷完鏈表，但是由于最后一次相加，導致有進位的情況
3.3 奇技淫巧
- 該技巧主要是用于消除header節點，這是一種類似于Linux內核單鏈表的實作思路
- 大致實作思路，請參照：https://www.cnblogs.com/wengle520/p/12296308.html
4. 實作
struct ListNode {
int val;
ListNode *next;
ListNode(int x) : val(x), next(NULL) {}
};
直觀演算法
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode header(-1);
int value = https://www.cnblogs.com/wengle520/p/0;
ListNode *prev = &header;
while(l1 && l2){
int v1 = l1->val;
int v2 = l2->val;
int sum = v1 + v2 + value;
int current_value = sum % 10;
value = sum / 10;
prev->next = new ListNode(current_value);
l1 = l1->next;
l2 = l2->next;
prev = prev->next;
}
while(l1){
int v = l1->val;
int sum = v + value;
int current_value = sum % 10;
value = sum / 10;
prev->next = new ListNode(current_value);
l1 = l1->next;
prev = prev->next;
}
while(l2){
int v = l2->val;
int sum = v + value;
int current_value = sum % 10;
value = sum / 10;
prev->next = new ListNode(current_value);
l2 = l2->next;
prev = prev->next;
}
if(value > 0){
prev->next = new ListNode(value);
}
return header.next;
}
};
簡潔演算法
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode header(-1);
int sum = 0;
ListNode *prev = &header;
while(l1 || l2 || sum > 0){
if(l1 != NULL){
sum += l1->val;
l1 = l1->next;
}
if(l2 != NULL){
sum += l2->val;
l2 = l2->next;
}
prev->next = new ListNode(sum%10);
prev = prev->next;
sum /= 10;
}
return header.next;
}
};
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91950.html
標籤：其他