给出两个非空的链表用来表示两个非负的整数。 其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位数字。 如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。 您可以假设除了数字 0 之外，这两个数都不会以 0 开头。 · 示例： 输入： (2 -> 4 -> 3) + (5 -> 6 -> 4) 输出： 7 -> 0 -> 8 原因： 342 + 465 =807 · 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/add-two-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目的思路很简单，难点在于链表操作，这题里面可以多写几个函数练练数据结构的基础知识。
注意：处理过程中，会出现输入为[1]、[9,9]的情况，相加结果为[0,0,1]，这要求我们增加一个进位标志flag，并学会手写链表元素的尾插法。
以下是在leetcode的提交代码。
class Solution { public: int length(ListNode* head) {//求链表长度的函数 int len = 0; ListNode* tmp = head; while (tmp != NULL) { len++; tmp = tmp->next; } return len; } ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { //链表相加的函数 ListNode* tmp; int len1 = length(l1),len2 = length(l2); int flag = 0; if (len1 >= len2) { tmp = l1; for (int i = 0; i < len1; i++) { if (i < len2) { l1->val += l2->val; l2 = l2->next; } l1->val += flag; flag = l1->val / 10; l1->val %= 10; if(i==len1-1 && flag){ //尾插法在链表尾部插入元素 l1 -> next = new ListNode; l1 -> next -> val = 1; l1 -> next ->next = NULL; } l1 = l1->next; } } else { tmp = l2; for (int i = 0; i < len2; i++) { if (i < len1) { l2->val += l1->val; l1 = l1->next; } l2->val += flag; flag = l2->val / 10; l2->val %= 10; if (i == len2 - 1 && flag) { l2->next = new ListNode; l2->next->val = 1; l2->next->next = NULL; } l2 = l2->next; } } return tmp; } };运行结果 运行结果分析 在程序中采用的length()函数，采用遍历的方法，大大增加了算法的时间复杂度，可以采用不求链表长度直接计算的方法（见leetcode相关评论）。此外，在链表数字求和的过程中，固定队长字串从头到尾进行了遍历时间复杂度固定为o(n)，可以增加一个break条件使程序在短数字链表相加完毕并进位完毕后直接结束遍历，这样可以使程序内加法模块的最佳时间复杂度为o(1)，最差时间复杂度为o(n)，大大提升运行效率。
//可增加的break语句，加上最优节省为原来运算时间的1/n if(i>shortListLength && !flag) break;关于链表的一些操作
