leetcode开篇~
问题描述：
You are given two linked lists representing two non-negative numbers. 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.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
首先要看懂题目，囧。第一次看，着实没有看懂。。
翻译一下：用两个链表表示两个非负整数。链表每个节点表示一个数字，按照数字倒序排列。比如123，用链表表示是3->2->1。求两个数字相加的和，并用链表表示。如342+465=807，用链表表示为7->0->8.
解答：
第一次写完使用的是递归的方式，结果显示超时。如下：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
return addTwoNumbers(l1, l2, false);
}
private static ListNode addTwoNumbers(ListNode l1, ListNode l2, boolean putMore){
if(l1 == null && l2 == null){
return putMore ? new ListNode(1) : null;
}else if(l1 == null){
return putMore ? addTwoNumbers(l2, new ListNode(1), false) : l2;
}else if(l2 == null){
return putMore ? addTwoNumbers(l1, new ListNode(1), false) : l1;
}
int value = putMore ? (l1.val+l2.val+1) : (l1.val+l2.val);
putMore = value >= 10 ? true : false;
ListNode result = new ListNode(value%10);
result.next = addTwoNumbers(l1.next, l2.next, putMore);
return result;
}
然后查看了其他人的解答，改为非递归方式：
public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head = new ListNode(0);
ListNode node = head;
ListNode p1 = l1;
ListNode p2 = l2;
boolean putMore = false;
while (p1 != null || p2 != null || putMore){
int add1 = p1 == null ? 0 : p1.val;
int add2 = p2 == null ? 0 : p2.val;
int value = putMore ? (add1+add2+1) : (add1+add2);
putMore = value >= 10 ? true : false;
node.next = new ListNode(value%10);
if(p1 != null) p1 = p1.next;
if(p2 != null) p2 = p2.next;
node = node.next;
}
return head.next;
}
加上测试代码：
private static ListNode initListNode(List<Integer> valueList){
ListNode result = new ListNode(valueList.get(0));
ListNode node = result;
for(int i=1; i<valueList.size(); i++){
node.next = new ListNode(valueList.get(i));
node = node.next;
}
return result;
}
private static List<Integer> getResult(ListNode node){
List<Integer> result = Lists.newArrayList();
ListNode temp = node;
while (temp != null){
result.add(temp.val);
temp = temp.next;
}
return result;
}
public static void main(String[] args) {
ListNode l1 = initListNode(Lists.newArrayList(6));
System.out.println("l1:" + JSON.toJSONString(getResult(l1)));
ListNode l2 = initListNode(Lists.newArrayList(6,9));
System.out.println("l2:" + JSON.toJSONString(getResult(l2)));
ListNode node = addTwoNumbers(l1, l2);
System.out.println("result:" + JSON.toJSONString(getResult(node)));
}
总结：
递归方式解答问题，比较容易想到。有了递归解答，要试着改成非递归的形式，提高性能。