有两个用链表表示的整数，每个结点包含一个数位。这些数位是反向存放的，也就是个位排在链表的首部。编写函数对这两个整数求和，并用链表形式返回结果。
给定两个链表ListNode* A，ListNode* B，请返回A+B的结果(ListNode*)。
{1,2,3},{3,2,1}
返回：{4,4,4}
本题的思路很简单，按照小学数学中学习的加法原理从末尾到首位，对每一位对齐相加即可。技巧在于如何处理不同长度的数字，以及进位和最高位的判断。这里对于不同长度的数字，我们通过将较短的数字补0来保证每一位都能相加。
/* struct ListNode { int val; struct ListNode *next; ListNode(int x) : val(x), next(NULL) {} };*/ class Plus { public: ListNode* plusAB(ListNode* a, ListNode* b) { /* int lena = getListLen(a); int lenb = getListLen(b); ListNode* p; int flag = 0; if(lena > lenb) { p = a; while(a != NULL) { if(b != NULL) { if (flag == 1) { p->val = p->val + a->val + 1; flag = 0; } else p->val = p->val + a->val; if(p->val >= 10) { p->val = p->val - 10; flag = 1; } p = p->next; b = b->next; } else { if(flag == 1) { p->val = p->val + 1; flag = 0; } if(p->val >= 10) { p->val = p->val - 10; flag = 1; } } } return a; } else { p = b; while(b != NULL) { if(a != NULL) { if(flag == 1) { p->val = p->val + a->val + 1; flag = 0; } else p->val = p->val + a->val; if(p->val >= 10) { p->val = p->val - 10; flag = 1; } p = p->next; a = a->next; } else { if(flag == 1) { p->val = p->val + 1; flag = 0; } if(p->val >= 10) { p->val = p->val - 10; flag = 1; } } } return b; } } int getListLen(ListNode* pHead) { ListNode* p = pHead; int count = 0; if(pHead == NULL) return 0; while(p != NULL) { count++; p = p->next; } return count; */ // 将较短的List的后面置为0 ListNode* head = new ListNode(-1); ListNode* p = head; ListNode* node = NULL; int c = 0, sum, vala, valb; ListNode *pa = a, *pb = b; while(pa != NULL || pb != NULL || c != 0) { vala = (pa == NULL)? 0: pa->val; valb = (pb == NULL)? 0: pb->val; sum = vala + valb + c; c = sum / 10; node = new ListNode(sum % 10); p->next = node; p = node; pa = (pa == NULL)? NULL: pa->next; pb = (pb == NULL)? NULL: pb->next; } return head->next; } };
原文：http://www.cnblogs.com/fengcq1129/p/4910481.html