Leetcode445

题意:You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first 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.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
【Leetcode445】思路一:两个链表分别反转,相加后,再反转,思路直接,但题目不允许
思路二:不反转,先统计两个链表长度,相等长度的低位段相加,向高位进位。
比价而言,方法二稍快,但是技巧复杂,容易出错。
其实我认为程序设计的关键在于能通过case的情况下,节约应试者的时间,且易于维护扩展。
方法二代码:

private static ListNode addTwoNumbers(ListNode l1, ListNode l2) { int len1 = 0; int len2 = 0; ListNode temp1 = l1; ListNode temp2 = l2; while (temp1 != null) { len1++; temp1 = temp1.next; } while (temp2 != null) { len2++; temp2 = temp2.next; }ListNode head = new ListNode(0); ListNode temp = head; temp.next = recur(l1, l2, len1, len2); if (temp.next.val >= 10) { temp.next.val = temp.next.val % 10; temp.val = 1; return head; } else { return head.next; } } //返回两个链表相加后的头部。 public static ListNode recur(ListNode l1, ListNode l2, int len1, int len2) { if (l1 == null && l2 == null) { return null; }ListNode l; ListNode next; int val; if (len1 == len2) { next = recur(l1.next, l2.next, len1 - 1, len2 - 1); val = l1.val + l2.val; } else if (len1 > len2) {//链表1比较长 next = recur(l1.next, l2, len1 - 1, len2); val = l1.val; } else {//链表2比较长 next = recur(l1, l2.next, len1, len2 - 1); val = l2.val; } if (next != null && next.val >= 10) { next.val = next.val % 10; val++; } l = new ListNode(val); l.next = next; return l; }

    推荐阅读