本类型博客中的各算法的时间复杂度分析均为博主自己推算，本类型博客也是博主自己刷LeetCode的自己的一些总结，因此个中错误可能较多，非常欢迎各位大神在博客下方评论，请不吝赐教

一、问题

输入：两个链表l1和l2，其中每个节点存储一个整数的某一位，从链表头开始依次位数升高输出：计算两个链表表示的整数的和，并将结果表示成链表输出

二、输入输出示例

输入：l1: 2->3->5, l2: 3->7->2输出：5->0->8

三、解法

本题的基本思路就是两个数加法的竖式计算。从低位到高位，对应位相加，如果大于10则向前进位，因此每个数位上的数=加数1对应位的数+加数2对应位的数+进位。由于遍历一遍即可，因此该题的解法的时间复杂度都是 O(n)

解法一：两个数同时遍历，中间不中断

解题思路：由于两个数的位数可能不同，因此遍历过程中可能会出现一个已经遍历结束，而另一个还有好多位没有处理。此时可以将位数较少的数高位填0，使其和另一个数位数相等，这样做算法较为简单，但是实际上增加了一些不必要的运算 package com.happy.leetcode.p2; import com.happy.leetcode.util.ListNode; /** * 64.08% * @author bird * */ public class AddTwoNumbersV1 { public static void main(String[] args) { int[] n1 = {1}; int[] n2 = {9, 9}; AddTwoNumbersV1 ins = new AddTwoNumbersV1(); ListNode l1 = ins.generateNodeByArray(n1); ListNode l2 = ins.generateNodeByArray(n2); ins.printListNode(l1); ins.printListNode(l2); ins.printListNode(ins.addTwoNumbers(l1, l2)); } private ListNode generateNodeByArray(int[] nums) { ListNode result = new ListNode(nums[nums.length-1]); ListNode tmp; for(int i=nums.length-2; i>=0; i--) { tmp = result; result = new ListNode(nums[i]); result.next = tmp; } return result; } private void printListNode(ListNode listNode) { while(listNode!=null) { System.out.print(listNode.val+" "); listNode = listNode.next; } System.out.println(); } public ListNode addTwoNumbers(ListNode l1, ListNode l2) { if(l1==null && l2==null) { return null; } if(l1==null) { return l2; } if(l2==null) { return l1; } int bitResult = l1.val+l2.val; int carry = bitResult/10; ListNode result = new ListNode(bitResult); ListNode last = result; ListNode next = null; l1 = l1.next; l2 = l2.next; int left = 0; int right = 0; while(l1!=null || l2!=null || carry!=0) { if(l1!=null) { left = l1.val; l1 = l1.next; }else { left = 0; } if(l2!=null) { right = l2.val; l2 = l2.next; }else { right = 0; } bitResult = left+right+carry; carry = bitResult/10; next = new ListNode(bitResult); last.next = next; last = next; } return result; } }

时间复杂度分析：遍历次数等于位数较多的那个数，因此时间复杂度位 O(max(n, m))

解法二：先遍历位数较少的数，另起循环遍历另一个数剩下的位数

解题思路：该解法中先同时遍历两个数，直到某一个数的位数用尽了。然后另起循环，遍历另一个数的剩余位，计算它们与进位相加后的结果。这样可以减少一些不必要的运算。另外在第二次遍历时，一旦在某位上进位终止了，即进位为0，而不是1时，则剩余的没有遍历的必要了，直接将剩余部分续接到结果链表末尾即可。

package com.happy.leetcode.p2; import com.happy.leetcode.util.ListNode; /**  * 64.08%  * @author bird  *  */ public class AddTwoNumbersV2 {          public static void main(String[] args) {         int[] n1 = {8, 6};         int[] n2 = {6, 4, 8};         AddTwoNumbersV2 ins = new AddTwoNumbersV2();         ListNode l1 = ins.generateNodeByArray(n1);         ListNode l2 = ins.generateNodeByArray(n2);         ins.printListNode(l1);         ins.printListNode(l2);         ins.printListNode(ins.addTwoNumbers(l1, l2));     }          private ListNode generateNodeByArray(int[] nums) {         ListNode result = new ListNode(nums[nums.length-1]);         ListNode tmp;         for(int i=nums.length-2; i>=0; i--) {             tmp = result;             result = new ListNode(nums[i]);             result.next = tmp;         }         return result;     }          private void printListNode(ListNode listNode) {         while(listNode!=null) {             System.out.print(listNode.val+"  ");             listNode = listNode.next;         }         System.out.println();     }     public ListNode addTwoNumbers(ListNode l1, ListNode l2) {         if(l1==null && l2==null) {             return null;         }         if(l1==null) {             return l2;         }         if(l2==null) {             return l1;         }                  int bitResult = l1.val+l2.val;         int carry = 0;         ListNode result = new ListNode(bitResult);         if(bitResult>=10) {             carry = 1;             result = new ListNode(bitResult-10);         }         ListNode last = result;         ListNode next = null;         l1 = l1.next;         l2 = l2.next;         while(l1!=null && l2!=null) {             bitResult = l1.val+l2.val+carry;             if(bitResult>=10) {                 carry = 1;                 next = new ListNode(bitResult-10);             }else {                 carry = 0;                 next = new ListNode(bitResult);             }             last.next = next;             last = next;             l1 = l1.next;             l2 = l2.next;         }         while(l1!=null) {             if(carry==0) {                 last.next = l1;                 break;             }             bitResult = l1.val+carry;             l1 = l1.next;             if(bitResult>=10) {                 carry = 1;                 next = new ListNode(bitResult-10);             }else {                 carry = 0;                 next = new ListNode(bitResult);             }             last.next = next;             last = next;         }         while(l2!=null) {             if(carry==0) {                 last.next = l2;                 break;             }             bitResult = l2.val+carry;             l2 = l2.next;             if(bitResult>=10) {                 carry = 1;                 next = new ListNode(bitResult-10);             }else {                 carry = 0;                 next = new ListNode(bitResult);             }             last.next = next;             last = next;         }         if(carry>0) {             next = new ListNode(carry);             last.next = next;         }         return result;     } } 时间复杂度分析：时间复杂度同上，为 O(max(n, m))