I am doing the LeetCode challenge 'Add Two Numbers'
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.
I was writing a solution, but observed some strange behavior which I am not able to comprehend. (I think the issue is in my for loop).
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1= reverseList(l1);
l2= reverseList(l2);
String str1 = returnListAsString(l1);
String str2 = returnListAsString(l2);
Integer int1 = Integer.valueOf(str1.toString());
Integer int2 = Integer.valueOf(str2.toString());
Integer sum = int1 int2;
System.out.println("sum.." sum);
char[] ch = String.valueOf(sum).toCharArray();
ListNode result = l1;
for (int i=0; i<ch.length; i ) {
System.out.println("test.." ch[i]);
result.val = ch[i];
System.out.println("test2.." result.val);
result = result.next;
}
return result;
}
public ListNode reverseList(ListNode l1) {
ListNode previous = null;
ListNode curr = l1;
ListNode next = null;
while (curr != null) {
next = curr.next;
curr.next = previous;
previous = curr;
curr = next;
}
l1 = previous;
return l1;
}
public String returnListAsString(ListNode l1) {
StringBuilder str1 = new StringBuilder();
while (l1 !=null) {
str1.append(l1.val);
l1 = l1.next;
}
return str1.toString();
}
}
Here is my input
[2,4,3] [5,6,4]
stdout
sum..807 test..8 test2..56 test..0 test2..48 test..7 test2..55
output
[]
I think the issue is inside my for loop. My question is, why does test and test2 not equal, and how can I have an output that at least says [8,0,7]?
CodePudding user response：
Your output for "test" prints a String representation of a character, your "test2" output prints the integer value of that character. The integer value of '0' is 48 (ASCII or UTF8-encoding).
You would have to parse back the char value to the proper int:
result.val = Integer.parseInt("" ch[i]);
Still a very complicated solution, and if @Abra is right, I would suggest that you don't convert the numbers to any object first, but add them digit by digit and keep the overflow (anything that is bigger than 9) for the next digit.
You still have to take care, when both numbers do not have the same length and that the overflow of the last digit of input is appended to the output.
This method would also save you from reversing the result again, it's output from the lowest significant value to the highest.
CodePudding user response：
I think the issue is inside my for loop
Definitely. You set result to l1. Then you assign result to result.next. Eventually you assign null to result. Hence your "empty" output. The first element in the char array, i.e. ch needs to become the last ListNode. The second element in ch needs to become the second last ListNode.
Here is my rewrite of your code:
public class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
l1 = reverseList(l1);
l2 = reverseList(l2);
String str1 = returnListAsString(l1);
String str2 = returnListAsString(l2);
Integer int1 = Integer.valueOf(str1.toString());
Integer int2 = Integer.valueOf(str2.toString());
Integer sum = int1 int2;
System.out.println("sum.." sum);
char[] ch = String.valueOf(sum).toCharArray();
ListNode result = null;
ListNode temp = new ListNode(ch[0] - '0');
for (int i = 1; i < ch.length; i ) {
System.out.println("test.." ch[i]);
result = new ListNode(ch[i] - '0', temp);
temp = result;
System.out.println("test2.." result.val);
}
return result;
}
public ListNode reverseList(ListNode l1) {
ListNode previous = null;
ListNode curr = l1;
ListNode next = null;
while (curr != null) {
next = curr.next;
curr.next = previous;
previous = curr;
curr = next;
}
l1 = previous;
return l1;
}
public String returnListAsString(ListNode l1) {
StringBuilder str1 = new StringBuilder();
while (l1 != null) {
str1.append(l1.val);
l1 = l1.next;
}
return str1.toString();
}
public static void main(String[] args) {
ListNode three = new ListNode(3);
ListNode four = new ListNode(4, three);
ListNode two = new ListNode(2, four);
ListNode fore = new ListNode(4);
ListNode six = new ListNode(6, fore);
ListNode five = new ListNode(5, six);
Solution soln = new Solution();
ListNode rslt = soln.addTwoNumbers(two, five);
System.out.println("Result: " soln.returnListAsString(rslt));
}
}
class ListNode {
int val;
ListNode next;
ListNode() {
this(0);
}
ListNode(int val) {
this(val, null);
}
ListNode(int val, ListNode next) {
this.val = val;
this.next = next;
}
}
Output when running the above code:
sum..807
test..0
test2..0
test..7
test2..7
Result: 708
I appreciate the responses and I realize my solution isn't optimal, but my original question is why the test and test2 values being returned in stdout are not equal?
I believe I have answered your question.