LeetCode-002两数相加(Add Two Numbers)

2019-06-20 23:32:04 3 分钟读完 (大约 420 个字)

Categories:

technology

Tags: BeInvisible, Java, LeetCode, 数据结构, 算法

LeetCode-002

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

Solution

class Solution {
	Integer carry=0;
	public ListNode addTwoNumbers(ListNode l1,ListNode l2) {
		ListNode sol=new ListNode(-1);
		ListNode solution=sol;
		if (l1==null||l2==null)
			return l1!=null?l1:l2;
		while (l1!=null) {
			if (l2!=null) {
				sol.next=new ListNode(l1.val+l2.val+carry);
				sol.next.val=plusCarry(sol.next.val);
				l1=l1.next;
				l2=l2.next;
			}
			else {
				sol.next=new ListNode(l1.val+carry);
				sol.next.val=plusCarry(sol.next.val);
				l1=l1.next;
			}
			sol=sol.next;
		}
		while (l2!=null||carry!=0) {
			sol.next=new ListNode((l2==null?0:l2.val)+carry);
			sol.next.val=plusCarry(sol.next.val);
			l2=l2==null?null:l2.next;
			sol=sol.next;
		}
		return solution.next;
	}
	public int plusCarry(int val) {
		if (val>=10) {
			val-=10;
			carry=1;
		}
		else 
			carry=0;
		return val;
	}
}

题目描述：
给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。

总结：

执行用时11 ms，在所有 Java 提交中击败了50.40%的用户。
内存消耗43.7 MB，在所有 Java 提交中击败了88.25%的用户。

效率不高，后面会进行改进并更新。

记：
刚开始刷LeetCode，选择Leetcode-cn，已经写过1,2,7,9,13,14,20,706八道，准备写 Top-100-liked-questions ，账户页面 https://leetcode-cn.com/u/v2beach/ ，尝试在csdn记录，欢迎互勉和监督。

LeetCode-002两数相加(Add Two Numbers)

评论

Your browser is out-of-date!