LeetCode2.两数相加

一看完题，我的想法是先算出这两个链表表示的数，然后相加，然后把这个数一位一位的分配给第三个数组，这种方法应该很简单但是要遍历三次数组，于是我就想直接一遍遍历，两个链表同时往后面遍历，把这两个数的和给第三个链表，如果有进位，下一个数加1；但是写完之后出现的问题，因为我的循环是先创建下一个链表然后，指针指向这个链表，然后再进行循环，但是这样就回造成最后面多了一个节点，我想改进一下的但是想不出来，就只能再遍历一遍把最后一个节点删除了，这样算法也不是很优了，以下是我的代码：

lass Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode h1 = l1;ListNode h2 = l2;if(h1 == null)return h2;if(h2 == null)return h1;ListNode h3 = new ListNode();ListNode l3 = h3;int jinwei=0;while(h1 !=null || h2!=null){int num1=0;int num2=0;if(h1!=null){num1 = h1.val;h1=h1.next;}if(h2!=null){num2 = h2.val;h2=h2.next;}int sum = num1+num2+jinwei;h3.val = sum % 10;jinwei = sum > 9 ? 1 : 0;h3.next = new ListNode(jinwei);h3 = h3.next;}h3 = l3;while(l3.next.next !=null){l3=l3.next;}if(l3.next.val == 0)l3.next=null;return h3;}}

然后我觉得这个算法还不如我一开始得想法，于是我就按照一开始得想法写了个代码，就是先算出他们表示那个数，然后和按位分给第三个数组，于是写下了这个代码：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {long sum = getValue(l1) + getValue(l2);if(sum == 0)return new ListNode(0);ListNode h3 = new ListNode();ListNode l3 = h3;while(sum != 0){h3.next = new ListNode();h3.next.val = (int)(sum % 10);sum = sum/10;h3 = h3.next;}return l3.next;}public long getValue(ListNode l){int pos =0;long value = 0;while(l !=null){value+=Math.pow(10,pos)*l.val;pos++;l=l.next;}return value;}}

前面得测试用例都过了，没想到后面那么大直接溢出了，

还是看看题解吧，题解的方法和我的方法差不多，但是它是用了一个判段是不是head来创建链表，然后拿到一个和就new 一个next节点并把和给它，然后当前指针移到他的下一个指针，如果遍历完了之后还有进位就再创建一个节点，并赋值1。我的是每次都会多创建一个节点，之后再遍历一次，如果最后那个节点是0就删了，如果是1就不删，所以我多了一遍遍历链表的过程。以下是题解代码：

class Solution {public ListNode addTwoNumbers(ListNode l1, ListNode l2) {ListNode head = null, tail = null;int carry = 0;while (l1 != null || l2 != null) {int n1 = l1 != null ? l1.val : 0;int n2 = l2 != null ? l2.val : 0;int sum = n1 + n2 + carry;if (head == null) {head = tail = new ListNode(sum % 10);} else {tail.next = new ListNode(sum % 10);tail = tail.next;}carry = sum / 10;if (l1 != null) {l1 = l1.next;}if (l2 != null) {l2 = l2.next;}}if (carry > 0) {tail.next = new ListNode(carry);}return head;}
}