|
| 1 | +packagemedium; |
| 2 | + |
| 3 | +importjava.util.ArrayList; |
| 4 | +importjava.util.Collections; |
| 5 | +importjava.util.List; |
| 6 | + |
| 7 | +importutils.CommonUtils; |
| 8 | +importclasses.ListNode; |
| 9 | + |
| 10 | +/**2. Add Two Numbers QuestionEditorial Solution My Submissions |
| 11 | +Total Accepted: 164672 |
| 12 | +Total Submissions: 675656 |
| 13 | +Difficulty: Medium |
| 14 | +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. |
| 15 | +
|
| 16 | +Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) |
| 17 | +Output: 7 -> 0 -> 8*/ |
| 18 | +publicclassAddTwoNumbers { |
| 19 | +//Last, I went to Discuss and like this solution the best: https://discuss.leetcode.com/topic/6220/my-accepted-java-solution |
| 20 | +//it's really much more concise and elegant: |
| 21 | +//we don't actually need to collect all values from each node out and put them into a list and then do calculations |
| 22 | +//I could get out of that thinking box, I could direclty manipulate the values from the nodes and do the computation, cool! |
| 23 | +publicListNodeaddTwoNumbers(ListNodel1,ListNodel2) { |
| 24 | +ListNodeprev =newListNode(0); |
| 25 | +ListNodehead =prev; |
| 26 | +intcarry =0; |
| 27 | +while(l1 !=null ||l2 !=null ||carry !=0){ |
| 28 | +ListNodecurr =newListNode(0); |
| 29 | +intsum = (l2 !=null ?l2.val :0) + (l1 !=null ?l1.val :0) +carry; |
| 30 | +curr.val =sum %10; |
| 31 | +carry =sum /10; |
| 32 | +prev.next =curr; |
| 33 | +prev =curr; |
| 34 | + |
| 35 | +l1 = (l1 ==null) ?l1 :l1.next; |
| 36 | +l2 = (l2 ==null) ?l2 :l2.next; |
| 37 | + } |
| 38 | +returnhead.next; |
| 39 | + } |
| 40 | + |
| 41 | +//then I came up with this approach: do addition digit by digit in the ArrayList, thus no matter how big the number is, it could always be computed |
| 42 | +publicListNodeaddTwoNumbers_ACed(ListNodel1,ListNodel2) { |
| 43 | +List<Integer>nums1 =newArrayList(); |
| 44 | +List<Integer>nums2 =newArrayList(); |
| 45 | +ListNodetmp1 =l1,tmp2 =l2; |
| 46 | +while(tmp1 !=null){ |
| 47 | +nums1.add(tmp1.val); |
| 48 | +tmp1 =tmp1.next; |
| 49 | + } |
| 50 | +while(tmp2 !=null){ |
| 51 | +nums2.add(tmp2.val); |
| 52 | +tmp2 =tmp2.next; |
| 53 | + } |
| 54 | + |
| 55 | +//we don't need to reverse the two lists, just start adding them up from index 0 |
| 56 | +List<Integer>shorter = (nums1.size() >nums2.size()) ?nums2 :nums1; |
| 57 | +List<Integer>longer = (shorter ==nums1) ?nums2 :nums1; |
| 58 | +int[]res =newint[longer.size()+1]; |
| 59 | +booleancarry =false; |
| 60 | +inti =0; |
| 61 | +for(;i <shorter.size();i++){ |
| 62 | +intthisResult =0; |
| 63 | +if(carry){ |
| 64 | +thisResult =shorter.get(i) +longer.get(i) +1; |
| 65 | + }else { |
| 66 | +thisResult =shorter.get(i) +longer.get(i); |
| 67 | + } |
| 68 | +if(thisResult >=10){ |
| 69 | +res[i] =Character.getNumericValue(String.valueOf(thisResult).charAt(1)); |
| 70 | +carry =true; |
| 71 | + }else { |
| 72 | +res[i] =thisResult; |
| 73 | +carry =false; |
| 74 | + } |
| 75 | + } |
| 76 | + |
| 77 | +if(shorter.size() ==longer.size()){ |
| 78 | +if(carry)res[i] =1; |
| 79 | + } |
| 80 | + |
| 81 | +for(;i <longer.size();i++){ |
| 82 | +intthisResult =0; |
| 83 | +if(carry){ |
| 84 | +thisResult =longer.get(i)+1; |
| 85 | + }else { |
| 86 | +thisResult =longer.get(i); |
| 87 | + } |
| 88 | +if(thisResult >=10){ |
| 89 | +res[i] =Character.getNumericValue(String.valueOf(thisResult).charAt(1)); |
| 90 | +carry =true; |
| 91 | + }else { |
| 92 | +res[i] =thisResult; |
| 93 | +carry =false; |
| 94 | + } |
| 95 | + } |
| 96 | +if(carry)res[i] =1; |
| 97 | + |
| 98 | +CommonUtils.printArray(res); |
| 99 | + |
| 100 | +ListNodepre =newListNode(-1); |
| 101 | +ListNodenext =newListNode(-1); |
| 102 | +pre.next =next; |
| 103 | +for(intj =0;j <res.length;){ |
| 104 | +next.val =res[j]; |
| 105 | +j++; |
| 106 | +if(j ==res.length-1 &&res[j] ==0)break; |
| 107 | +if(j <res.length) |
| 108 | +next.next =newListNode(-1); |
| 109 | +next =next.next; |
| 110 | + } |
| 111 | +returnpre.next; |
| 112 | + } |
| 113 | + |
| 114 | +publicstaticvoidmain(String...strings){ |
| 115 | +// ListNode l1 = new ListNode(2); |
| 116 | +// l1.next = new ListNode(4); |
| 117 | +// l1.next.next = new ListNode(3); |
| 118 | +// ListNode l2 = new ListNode(5); |
| 119 | +// l2.next = new ListNode(6); |
| 120 | +// l2.next.next = new ListNode(4); |
| 121 | + |
| 122 | +// ListNode l1 = new ListNode(5); |
| 123 | +// ListNode l2 = new ListNode(5); |
| 124 | + |
| 125 | +ListNodel1 =newListNode(1); |
| 126 | +ListNodel2 =newListNode(9); |
| 127 | +l2.next =newListNode(9); |
| 128 | + |
| 129 | +AddTwoNumberstest =newAddTwoNumbers(); |
| 130 | +ListNoderesult =test.addTwoNumbers_ACed(l1,l2); |
| 131 | +CommonUtils.printList(result); |
| 132 | + } |
| 133 | + |
| 134 | +//the most naive approach will result in overflow/NumberFormatException, since if the number is greater than 2^64, it won't work |
| 135 | +//sample test case: [9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9] |
| 136 | +// [1] |
| 137 | +publicListNodeaddTwoNumbers_overflowed(ListNodel1,ListNodel2) { |
| 138 | +longnum1 =0,num2 =0; |
| 139 | +List<Integer>nums1 =newArrayList(); |
| 140 | +List<Integer>nums2 =newArrayList(); |
| 141 | +ListNodetmp1 =l1,tmp2 =l2; |
| 142 | +while(tmp1 !=null){ |
| 143 | +nums1.add(tmp1.val); |
| 144 | +tmp1 =tmp1.next; |
| 145 | + } |
| 146 | +while(tmp2 !=null){ |
| 147 | +nums2.add(tmp2.val); |
| 148 | +tmp2 =tmp2.next; |
| 149 | + } |
| 150 | +StringBuildersb =newStringBuilder(); |
| 151 | +for(inti =nums1.size()-1;i >=0;i--){ |
| 152 | +sb.append(nums1.get(i)); |
| 153 | + } |
| 154 | +num1 =Long.valueOf(sb.toString()); |
| 155 | +sb.setLength(0); |
| 156 | +for(inti =nums2.size()-1;i >=0;i--){ |
| 157 | +sb.append(nums2.get(i)); |
| 158 | + } |
| 159 | +num2 =Long.valueOf(sb.toString()); |
| 160 | +longres =num1 +num2; |
| 161 | +StringresStr =String.valueOf(res); |
| 162 | +sb.setLength(0); |
| 163 | +Stringreverse =sb.append(resStr).reverse().toString(); |
| 164 | +char[]chars =reverse.toCharArray(); |
| 165 | +ListNodedummy =newListNode(-1); |
| 166 | +ListNoderesult =newListNode(-1); |
| 167 | +dummy.next =result; |
| 168 | +for(inti =0;i <chars.length;i++){ |
| 169 | +result.val =Character.getNumericValue(chars[i]); |
| 170 | +if(i <chars.length-1) |
| 171 | +result.next =newListNode(-1); |
| 172 | +result =result.next; |
| 173 | + } |
| 174 | +returndummy.next; |
| 175 | + } |
| 176 | + |
| 177 | +} |