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 contains a single digit. Add the two numbers and return the sum as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
递归,每次递归时建立root的next节点,然后将root移动到root.next。 计算两个节点的和并填入root节点。每次计算时需要计算是否进位。 递归两个节点的next节点,并将carry传入。 当一个节点为null时,只递归和计算另一个节点。 当两个节点为null时,如果有carry需要将其放入新节点,如果没有则返回。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 class Solution { public ListNode addTwoNumbers (ListNode l1, ListNode l2) { ListNode root = new ListNode (); addTwo(l1,l2,root,0 ); return root.next; } private void addTwo (ListNode l1, ListNode l2, ListNode root, int carry) { if (l1 == null && l2 == null && carry == 0 ){ return ; } else if (l1 == null && l2 == null ){ root.next = new ListNode (); root = root.next; root.val = carry; return ; } else if (l1 == null ){ root.next = new ListNode (); root = root.next; root.val = (l2.val + carry) % 10 ; carry = (l2.val + carry) / 10 ; addTwo(null , l2.next, root, carry); return ; } else if (l2 == null ){ root.next = new ListNode (); root = root.next; root.val = (l1.val + carry) % 10 ; carry = (l1.val + carry) / 10 ; addTwo(null , l1.next, root, carry); return ; } root.next = new ListNode (); root = root.next; root.val = (l1.val + l2.val + carry) % 10 ; carry = (l1.val + l2.val + carry) / 10 ; addTwo(l1.next, l2.next, root, carry); } }