Hi I'm trying to solve some problem and having trouble identifying my mistake.. :(
The description of the problem:
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.
Example:
Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 465 = 807.
My code:
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
String firstNumber = "";
String secondNumber = "";
// Converts the lists into strings
while (l1 != null){
firstNumber = Integer.toString(l1.val);
l1 = l1.next;
}
while (l2 != null){
secondNumber = Integer.toString(l2.val);
l2 = l2.next;
}
// Reverses the strings
firstNumber = new StringBuilder(firstNumber).reverse().toString();
secondNumber = new StringBuilder(secondNumber).reverse().toString();
long additionLong = Long.parseLong(firstNumber) Long.parseLong(secondNumber);
ListNode solutionList = new ListNode();
ListNode prevNode = new ListNode();
ListNode currentNode = solutionList;
while (additionLong > 0){
currentNode.val = (int) additionLong % 10;
additionLong /= 10;
ListNode nextNode = new ListNode();
currentNode.next = nextNode;
prevNode = currentNode;
currentNode = currentNode.next;
}
prevNode.next = null;
return solutionList;
}
}
I'm having trouble passing the following test and I can't seem to identify the problem..
Input
l1 = [9]
l2 = [1,9,9,9,9,9,9,9,9,9]
My Output
[8,0,0,0,0,0,0,0,0,0,1]
Expected
[0,0,0,0,0,0,0,0,0,0,1]
I suspect the troublesome step is when I add the two reversed strings together, but the code does pass some of the other tests so I don't quiet get why it won't pass this one..
Also, so far in my degree we've only had 2 very basic introductionery courses in Java and C and we only covered the basics, so we didn't really learn how to write code well.. if I did something silly in my code please let me know so I know to avoid it. :)
CodePudding user response：
Your approach seems somewhat complicated. You're doing an arithmetic problem; it's probably not the right approach to involve Strings.
Think about how you (perhaps) learned to do addition in primary school: you add the columns, starting at the least-significant digits, carrying any amount over 10 to the next column.
The problem here is simplified by the fact the least-significant digits come first. So, you just need to create a new node for the current column, calculate its value, and carry anything over to the next column.
It's slightly complicated by the fact the lists can be differing lengths, but that's not too hard to deal with: if you've "run out" of digits in one list, you can just pretend it contains a zero.
This code will just print out the digits of the sum; if desired, you should try to to work out how to build a linked list containing the result instead:
int carry = 0;
// We want to iterate while there is something more to add - even if
// we have exceeded the length of one or both lists, we may still have carry.
while (l1 != null || l2 != null || carry != 0) {
// Get the value from each of the lists. If we've gone past the end of
// a list, just use zero as the value.
int i1 = l1 != null ? l1.value : 0;
int i2 = l2 != null ? l2.value : 0;
int value = i1 i2 carry;
// The next carry is the tens of value.
carry = value / 10;
// The value in the current column are the units of value.
value = value % 10;
// Print out the value in the current column.
System.out.println(value);
// Advance the two linked lists (assuming we've not reached the end already).
if (l1 != null) l1 = l1.next;
if (l2 != null) l2 = l2.next;
}
CodePudding user response：
After you converted the lists into strings you have:
String firstNumber = "243"; //or firstNumber = "9";
String secondNumber = "564";//secondNumber = "1999999999";
// Reverses the strings
firstNumber = new StringBuilder(firstNumber).reverse().toString();
secondNumber = new StringBuilder(secondNumber).reverse().toString();
//add
Long sum = Long.valueOf(firstNumber) Long.valueOf(secondNumber);
//reverse sum
String output = new StringBuilder(String.valueOf(sum)).reverse().toString();
System.out.println(output);
If you need to split the output into an array simply change it to :
//reverse sum and split it
String[] output = new
StringBuilder(String.valueOf(sum)).reverse().toString().split("");
System.out.println(Arrays.toString(output));
CodePudding user response：
If you have a hammer every problem looks like a nail.
Using String is the same.
Rather show a more abstract approach.
If you have 67 [7, 6] and 398 [8, 9, 3] how would you add?
- 7 8 giving 5 with carry 1
- 6 9 carry giving 6 with carry 1
- N/A 3 carry giving 4 with carry 0
- N/A N/A carry giving N/A
So:
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode sum = null;
ListNode last = null;
int carry = 0;
while (l1 != null && l2 != null) {
int sum = carry;
if (l1 != null) {
sum = l1.value;
l1 = l1.next;
}
if (l2 != null) {
sum = l2.value;
l2 = l2.next;
}
carry = 0;
if (sum >= 10) {
carry = 1;
sum -= 10;
}
ListNode sumNode = ...
...
}
if (carry != 0) { // An extra digit.
...
}
return sum;
}
CodePudding user response：
if I did something silly in my code please let me know so I know to avoid it.
There is a problem in casting a result to long:
currentNode.val = (int) additionLong % 10;
This will cast additionLong to int which will lead to loss, and only then % 10 is applied to that. You need:
currentNode.val = (int) (additionLong % 10);
This will fix the issue for this particular test case.
As others have said you should consider doing this without converting between linked list, string, and long. You may bump into a test case for which the capacity of long is not enough, and then you'll be really stuck.
Instead stick with linked lists only, processing digit by digit. That is the purpose of the exercise.