收获：1、程序调试一定要根据结果推理，不能乱试，至少要有根据的试
2、单向链表遍历的时候要注意: 不能找到之前的元素。这样，在遍历到list末尾的时候，就不能给list添加元素了。
Problem: You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8思路：链表对应的位置相加即可。
难点：1、加法的进位处理；
2、两个链表的遍历过程中在末尾如何处理。
代码：
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 ListNode* initList();10 void listAdd(ListNode* last, int val);11 class Solution {12 public:13 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {14 // IMPORTANT: Please reset any member data you declared, as15 // the same Solution instance will be reused for each test case.16 ListNode *L1 = l1;17 ListNode *L2 = l2;18 ListNode *temp = NULL; // to keep the L1 finding the list's end 19 int increase = 0;20 while(L1 || L2 || increase){21 if(L1 && L2){ // L1 and L2 are not empty22 int sum_val = L1->val + L2->val + increase;23 L1->val = sum_val % 10;24 increase = sum_val / 10;25 temp = L1; // in case of L1 is the end of list26 L1 = L1->next;27 L2 = L2->next;28 }else if((NULL == L1) && (NULL != L2)){ // L1 empty29 L1 = new ListNode(0);30 temp->next = L1;31 int sum_val = L2->val + increase;32 L1->val = sum_val % 10;33 increase = sum_val/10;34 temp = L1;35 L1 = L1->next;36 L2 = L2->next;37 }38 else if((NULL != L1) && (NULL == L2)){39 int sum_val = L1->val + increase;40 L1->val = sum_val % 10;41 increase = sum_val /10;42 temp = L1;43 L1 = L1->next;44 }45 else if(increase){46 L1 = new ListNode(1);47 temp->next = L1;48 //L1 = temp;49 //L1->val = 1;50 increase = 0;51 L1 = L1->next;52 }53 }54 return l1;55 }56 };
这个程序破坏了输入链表。这不好（根据Code Complete2）。下面的程序应该也可以。
1 /** 2 * Definition for singly-linked list. 3 * struct ListNode { 4 * int val; 5 * ListNode *next; 6 * ListNode(int x) : val(x), next(NULL) {} 7 * }; 8 */ 9 ListNode* initList();10 void listAdd(ListNode* last, int val);11 class Solution {12 public:13 ListNode *addTwoNumbers(ListNode *l1, ListNode *l2) {14 // IMPORTANT: Please reset any member data you declared, as15 // the same Solution instance will be reused for each test case.16 if((!l1) && (!l2)) return NULL;17 ListNode *L1 = l1;18 ListNode *L2 = l2;19 ListNode *res = new ListNode(0);20 ListNode *last = res;21 ListNode *temp = res;22 int flag = 0;23 24 while(L1 || L2 || flag){25 if(L1 && L2){ // L1 and L2 are not empty26 int sum_val = L1->val + L2->val + flag;27 if(NULL == last){ 28 last = new ListNode(sum_val % 10);29 temp->next = last;30 temp = last;31 }else{32 last->val = (sum_val % 10); //33 }34 flag = sum_val/10;35 last = last->next;36 L1 = L1->next;37 L2 = L2->next;38 }else if((NULL == L1) && (NULL != L2)){39 int sum_val = L2->val + flag;40 if(NULL == last){41 last = new ListNode(sum_val % 10);42 temp->next = last;43 temp = last;44 }else{45 last->val = (sum_val % 10);46 }47 flag = sum_val/10;48 last = last->next;49 L2 = L2->next;50 }51 else if((NULL != L1) && (NULL == L2)){52 L2 = L1;53 L1 = NULL;54 }55 else if(flag){56 last = new ListNode(1);57 temp->next = last;58 flag = 0;59 }60 }61 return res; 62 }63 };