博文中会简要介绍Leetcode P0002题目分析及解题思路。
“Add Two Numbers”是一道很经典的题目，题干易懂。要求按十进制加法，加和两个倒序排列的LinkedList形成一个新的LinkedList。
You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
可以预料复杂度是O(n)。同时按序扫描两个LinkedList中的值，将其加和。优化点在于减少串行的循环，将代码控制在一个循环内解决。则涉及的重点在于判断循环边界条件。两个主要条件，l1或l2非空，或者进位不为0。
通过设置一个dummy的LinkedList指针头来简化返回结果的操作。
以下是Java的题解代码实现。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
if (l1 == null || l2 == null)
return (l1 != null)? l1: l2;
ListNode dummy = new ListNode(0);
ListNode tail = dummy;
int increment = 0;
while (l1 != null || l2 != null || increment > 0) {
// 如果l1非空则根据l2来加和，若为空则取决于l2
int newValue = (l1 != null? (l2 != null? l1.val+l2.val: l1.val): (l2 != null? l2.val: 0)) + increment;
ListNode l3 = new ListNode(newValue % 10);
increment = newValue / 10;
tail.next = l3;
tail = tail.next;
l1 = (l1 != null)? l1.next: null;
l2 = (l2 != null)? l2.next: null;
}
return dummy.next;
}
}
以下是C++的题解代码实现。
/**
* 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) {
if (l1 == NULL || l2 == NULL)
return l1? l1: l2;
ListNode* dummy = new ListNode(0);
ListNode* tail = dummy;
int increment = 0;
while (l1 || l2 || increment) {
int new_val = (l1? (l2? l1->val+l2->val: l1->val): (l2? l2->val: 0)) + increment;
ListNode* l3 = new ListNode(new_val % 10);
increment = new_val / 10;
tail->next = l3;
tail = tail->next;
l1 = l1? l1->next: NULL;
l2 = l2? l2->next: NULL;
}
return dummy->next;
}
};