本文主要是介绍LeetCode--2.Add Two Numbers 445. Add Two Numbers II 989. Add to Array-Form of Integer，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题链接：
https://leetcode.com/problems/add-two-numbers/
https://leetcode.com/problems/add-two-numbers-ii/
https://leetcode.com/problems/add-to-array-form-of-integer/
这三个问题都是基于特殊数据结构的加法运算。需要注意整数int的范围和加法进位操作的表达。
问题一：基于链表存储的整数加法，数字从低位到高位依次存储在链表中，这是我的代码，有点丑陋，效率较低。
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode p1=l1;ListNode p2=l2;int sign=0;int temp=0;ListNode r=new ListNode(1);ListNode p3=r;while(p1!=null || p2!=null){if(p1==null)p1=new ListNode(0);if(p2==null)p2=new ListNode(0);temp=p1.val+p2.val+sign;if(temp>=10){sign=1;temp-=10;}elsesign=0;p3.next=new ListNode(temp);if(p2.next==null && sign==1){p3.next.next=new ListNode(1);}p3=p3.next;p1=p1.next;p2=p2.next;}return r.next;}
}Solutions里面的解法思路基本一致，但是处理的非常优雅：
有些tricks十分值得学习：虚拟头节点的加入，空节点统一处理为加上0。
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode dummyHead = new ListNode(0);ListNode p = l1, q = l2, curr = dummyHead;int carry = 0;while (p != null || q != null) {int x = (p != null) ? p.val : 0;int y = (q != null) ? q.val : 0;int sum = carry + x + y;carry = sum / 10;curr.next = new ListNode(sum % 10);curr = curr.next;if (p != null) p = p.next;if (q != null) q = q.next;}if (carry > 0) {curr.next = new ListNode(carry);}return dummyHead.next;
}问题二：这个问题与第一问的区别是：数字从高位到低位依次存储在链表中，而链表的遍历只能从头到尾遍历，跟问题一一个解法，先上我捉急的代码：
class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {if(l1==null)return l2;if(l2==null)return l1;int len1=1,len2=1,temp=0;ListNode p1=l1,p2=l2;while(p1.next!=null){p1=p1.next;len1++;}while(p2.next!=null){p2=p2.next;len2++;}if(len1<len2){p1=l2;p2=l1;temp=len1;len1=len2;len2=temp;}else{p1=l1;p2=l2;}ListNode[] arr=new ListNode[len1+1];arr[0]=new ListNode(0);int i=1;while(len1!=len2){arr[i]=new ListNode(p1.val);p1=p1.next;len1--;i++;}while(len1>0){arr[i]=new ListNode(p1.val+p2.val);i++;p1=p1.next;p2=p2.next;len1--;}for(int j=arr.length-1;j>0;j--){if(arr[j].val>=10){arr[j-1].val+=1;arr[j].val-=10;}}if(arr[0].val!=0){for(i=0;i<arr.length-1;i++){arr[i].next=arr[i+1];}return arr[0];}else{for(i=1;i<arr.length-1;i++){arr[i].next=arr[i+1];}return arr[1];}}
}我的解法十分粗暴，因为是一年前刚开始刷LeetCode时写的，那时候有思路能AC就很不错了。更高效的处理方式是借助栈来从个位开始计算：
public class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {Stack<Integer> s1 = new Stack<Integer>();Stack<Integer> s2 = new Stack<Integer>();while(l1 != null) {s1.push(l1.val);l1 = l1.next;};while(l2 != null) {s2.push(l2.val);l2 = l2.next;}int sum = 0;ListNode list = new ListNode(0);while (!s1.empty() || !s2.empty()) {if (!s1.empty()) sum += s1.pop();if (!s2.empty()) sum += s2.pop();list.val = sum % 10;ListNode head = new ListNode(sum / 10);head.next = list;list = head;sum /= 10;}return list.val == 0 ? list.next : list;}
}问题三：
思路一：在参加LeetCode contest遇到一道很脏的easy题目，边界条件处理起来比较痛苦（可能我没想到更好的方法，所以处理起来很暴力），代码如下：
class Solution {public List<Integer> addToArrayForm(int[] A, int K) {LinkedList<Integer> ret=new LinkedList<>();boolean flag=false;ArrayList<Integer> arr=new ArrayList<>();while(K!=0){arr.add(0,K%10);K/=10;}int[] B=new int[arr.size()];for(int i=0;i<arr.size();i++)B[i]=arr.get(i);if(A.length<B.length){int[] tmp=B;B=A;A=tmp;}int j=A.length-1;int k=B.length-1;while(j>=0 && k>=0){if(flag){A[j] += B[k]+1;flag=false;}elseA[j] += B[k];if(A[j]>=10){A[j]-=10;flag=true;}k--;j--;}while(j>=0){if(flag){A[j]+=1;flag=false;}elsebreak;if(A[j]>=10){A[j]-=10;flag=true;}j--;}if(flag)ret.add(1);for(int i:A)ret.add(i);return ret;}
}后来这个问题我看了Solutions觉得十分佩服，观察和思路都十分细腻，借鉴问题一的代码风格，该算法如下：
class Solution {public List<Integer> addToArrayForm(int[] A, int K) {LinkedList<Integer> ret=new LinkedList<>();int i=A.length-1;while(K!=0 || i>=0){int p=i>=0?A[i]:0;ret.add(0,(K+p)%10);K=(K+p)/10;i--;}return ret;}
}写出这样简洁的代码才让我感觉这是一道easy的问题，思路一的代码提交了5次才过也是没谁了。
这篇关于LeetCode--2.Add Two Numbers 445. Add Two Numbers II 989. Add to Array-Form of Integer的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
