patternjavaMinor
Linked list arithmetic
Viewed 0 times
listlinkedarithmetic
Problem
I am practicing for interviews and I tried solving the problem on my own and got a solution. I was wondering how can I improve the performance and memory on this program?
The problem performs addition on linked list nodes. The nodes are
Example:
Linked list output:
Here is my code:
Here is my linked list class:
```
public class LinkedListNode {
LinkedListNode next;
int value;
publ
The problem performs addition on linked list nodes. The nodes are
1s->10s->100s->.... The goal of this program is to perform addition on two of these linked lists. The output should be a linked list of the same format.Example:
1 -> 4 -> 3
+ 1 -> 5 -> 9 -> 2Linked list output:
2 -> 9 -> 2 -> 3Here is my code:
public class prob2_5 {
/*
* You have two numbers represented by a linked list, where each node contains a single digit.
* The digits are stored in reverse order, such that the 1's digit is at the head of the list.
* Write a function that adds the two numbers and returns the sum as a linked list
*
*/
public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
int l1sum = 0;
int l2sum = 0;
int multiplier = 1;
while(l1 != null) {
l1sum = l1sum + l1.value*multiplier;
multiplier = multiplier*10;
l1 = l1.next;
}
multiplier = 1;
while(l2 != null) {
l2sum = l2sum + l2.value*multiplier;
multiplier = multiplier*10;
l2 = l2.next;
}
int total = l2sum + l1sum;
char[] totalnum = (total + "").toCharArray();
int len = totalnum.length;
LinkedListNode tail = new LinkedListNode(totalnum[len - 1] - '0');
LinkedListNode newNode;
LinkedListNode prevNode = tail;
System.out.print(totalnum);
for (int i = len - 2; i >= 0; i--) {
newNode = new LinkedListNode(totalnum[i] - '0');
prevNode.next = newNode;
prevNode = newNode;
}
return tail;
}
}Here is my linked list class:
```
public class LinkedListNode {
LinkedListNode next;
int value;
publ
Solution
I believe you are missing the point of the exercise - instead of 'decoding' the input numbers, and then 're-encoding' the output number - you are supposed to iteratively get to the answer by going over the nodes of both lists:
public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
return addLists(0, l1, l2);
}
private static LinkedListNode addLists(int carryOver, LinkedListNode l1, LinkedListNode l2) {
// stop conditions
if (l1 == null && l2 == null && carryOver == 0) {
return null;
}
if (l1 == null) {
l1 = new LinkedListNode(0);
}
if (l2 == null) {
l2 = new LinkedListNode(0);
}
// iteration
int addedValue = l1.value + l2.value + carryOver;
carryOver = 0;
if (addedValue >= 10) {
addedValue -= 10;
carryOver = 1;
}
l3 = new LinkedListNode(addedValue);
// recursion
l3.next = addLists(carryOver, l1.next, l2.next);
return l3;
}Code Snippets
public static LinkedListNode addLists(LinkedListNode l1, LinkedListNode l2) {
return addLists(0, l1, l2);
}
private static LinkedListNode addLists(int carryOver, LinkedListNode l1, LinkedListNode l2) {
// stop conditions
if (l1 == null && l2 == null && carryOver == 0) {
return null;
}
if (l1 == null) {
l1 = new LinkedListNode(0);
}
if (l2 == null) {
l2 = new LinkedListNode(0);
}
// iteration
int addedValue = l1.value + l2.value + carryOver;
carryOver = 0;
if (addedValue >= 10) {
addedValue -= 10;
carryOver = 1;
}
l3 = new LinkedListNode(addedValue);
// recursion
l3.next = addLists(carryOver, l1.next, l2.next);
return l3;
}Context
StackExchange Code Review Q#41090, answer score: 8
Revisions (0)
No revisions yet.