Facebook Interview Question
InternsCountry: United States
Am I missing something here? I think this will add the wrong digit and produce the wrong result. For example, 4931 + 813, this will add 4 and 8. Unless you reverse both the linklists first, no?
import java.io.*;
import java.util.*;
class MyCode {
public static void main (String[] args) {
LinkedList<Integer> first = new LinkedList<Integer>();
LinkedList<Integer> second = new LinkedList<Integer>();
first.addFirst(4);
first.addFirst(9);
first.addFirst(3);
first.addFirst(1);
second.addFirst(8);
second.addFirst(1);
second.addFirst(3);
second.addFirst(3);
second.addFirst(3);
LinkedList<Integer> sum = MyCode.sum(first, second);
for(Integer i: sum) {
System.out.print(i);
}
System.out.println("expected: " + (1394+33318));
}
public static LinkedList<Integer> sum(LinkedList first, LinkedList second) {
Iterator<Integer> firstIterator = first.descendingIterator();
Iterator<Integer> secondIterator = second.descendingIterator();
LinkedList<Integer> ret = new LinkedList<Integer>();
int rest = 0;
while(firstIterator.hasNext() || secondIterator.hasNext()) {
Integer a = firstIterator.hasNext() ? firstIterator.next() : 0;
Integer b = secondIterator.hasNext() ? secondIterator.next() : 0;
ret.addFirst((a+b+rest)%10);
rest = (a + b + rest) / 10;
}
return ret;
}
}
import java.util.*;
public class HelloWorld{
public static void main(String []args){
LinkedList<Integer> obj1 = new LinkedList<Integer> ();
LinkedList<Integer> obj2 = new LinkedList<Integer> ();
LinkedList<Integer> res = new LinkedList<Integer> ();
int maxlen,minlen;
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj2.add(3);
obj2.add(9);
obj2.add(2);
if (obj1.size() <= obj2.size())
{
maxlen = obj1.size();
minlen = obj2.size();
}
else
{
maxlen = obj2.size();
minlen = obj1.size();
}
int carry = 0;
for(int i=maxlen-1;i>=0;i--)
{
int tmp1 = obj1.get(i);
int tmp2 = obj2.get(i);
int tmp3 = tmp1+tmp2+carry;
carry = 0;
if (tmp3 >= 10)
{
carry = (tmp3/10)%10;
tmp3 = tmp3%10;
}
res.addFirst(tmp3);
}
if (obj1.size() > obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj1.get(i);
int tmp2 = tmp1 +carry;
carry = 0;
if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
res.addFirst(tmp2);
}
if(carry !=0)
res.addFirst(carry);
}
else if (obj1.size() < obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj2.get(i);
int tmp2 = tmp1 +carry;
carry = 0;
if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
res.addFirst(tmp2);
}
if(carry !=0)
res.addFirst(carry);
}
else if((obj1.size() == obj2.size()) && (carry !=0))
{
res.addFirst(carry);
}
System.out.println("Result: " +res);
}
}
This could be made better of course but a linear algorithm thats easy I guess.
import java.util.*;
public class HelloWorld{
public static void main(String []args){
LinkedList<Integer> obj1 = new LinkedList<Integer> ();
LinkedList<Integer> obj2 = new LinkedList<Integer> ();
LinkedList<Integer> res = new LinkedList<Integer> ();
int maxlen,minlen;
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj1.add(9);
obj2.add(3);
obj2.add(9);
obj2.add(2);
if (obj1.size() <= obj2.size())
{
maxlen = obj1.size();
minlen = obj2.size();
}
else
{
maxlen = obj2.size();
minlen = obj1.size();
}
int carry = 0;
for(int i=maxlen-1;i>=0;i--)
{
int tmp1 = obj1.get(i);
int tmp2 = obj2.get(i);
int tmp3 = tmp1+tmp2+carry;
carry = 0;
if (tmp3 >= 10)
{
carry = (tmp3/10)%10;
tmp3 = tmp3%10;
}
res.addFirst(tmp3);
}
if (obj1.size() > obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj1.get(i);
int tmp2 = tmp1 +carry;
carry = 0;
if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
res.addFirst(tmp2);
}
if(carry !=0)
res.addFirst(carry);
}
else if (obj1.size() < obj2.size())
{
for(int i =maxlen; i< minlen;i++)
{
int tmp1 = obj2.get(i);
int tmp2 = tmp1 +carry;
carry = 0;
if(tmp2 >= 10)
{
carry = (tmp2/10)%10;
tmp2 = tmp2%10;
}
res.addFirst(tmp2);
}
if(carry !=0)
res.addFirst(carry);
}
else if((obj1.size() == obj2.size()) && (carry !=0))
{
res.addFirst(carry);
}
System.out.println("Result: " +res);
}
}
def addAsList(num1, num2):
#num1 = [1,2,3] as 123
ret = []
n1 = len(num1)
n2 = len(num2)
inc = 0
for i in range(n1):
v1 = num1[n1-i-1]
if n2-i <= 0:
num1[n1-i-1]+=inc
ret =num1[0:n1-i-1]+ret
inc = 0
break
v2 = num2[n2-i-1]
sum = v1+v2+inc
inc = sum/10
sum = sum%10
ret = [sum]+ret
if n2>n1:
num2[n2-n1]+=inc
ret = num2[0:n2-n1]+ ret
inc = 0
if inc > 0:
ret = [inc] + ret
return ret
public static LinkedList<Byte> sumOfLists(LinkedList<Byte> one, LinkedList<Byte> two) {
LinkedList<Byte> result = new LinkedList<>();
ListIterator<Byte> iterator1 = one.listIterator(one.size());
ListIterator<Byte> iterator2 = two.listIterator(one.size());
int rest = 0;
while (iterator2.hasPrevious() && iterator2.hasPrevious()) {
Byte number1 = iterator1.previous();
Byte number2 = iterator2.previous();
int sum = number1 + number2 + rest;
rest = sum / 10;
result.addFirst((byte) (sum % 10));
}
ListIterator<Byte> restIterator = null;
if (iterator1.hasPrevious()) {
restIterator = iterator1;
} else if (iterator2.hasPrevious()) {
restIterator = iterator2;
}
if (restIterator != null) {
while (restIterator.hasPrevious()) {
Integer sum = restIterator.previous() + rest;
rest = sum / 10;
result.addFirst((byte) (sum % 10));
}
}
if (rest > 0) {
result.addFirst((byte) rest);
}
return result;
}
Same as the problem 2.4 in Cracking the Coding Interview with the twist the most significant digit is "first" (I am assuming this means it is in the head of the list). Here it is my iterative version (instead of the recursive solution in the book):
class Node:
def __init__(self, value):
self.value = value
self.next = None
def gen_list(num):
last = Node(num[0])
start = last
for digit in num[1:]:
node = Node(digit)
last.next = node
last = node
return start
def print_list(num):
if num is None:
print('')
return
string = '{}'.format(num.value)
num = num.next
while num is not None:
string += ' -> {}'.format(num.value)
num = num.next
print(string)
def reverse_list(fwd):
last = None
while fwd is not None:
bwd = Node(fwd.value)
if last is not None:
bwd.next = last
last = bwd
fwd = fwd.next
return last
def sum_reverse_list(node1, node2):
c = 0
node = None
prev = None
while node1 is not None or\
node2 is not None:
a = node1.value if node1 is not None else 0
b = node2.value if node2 is not None else 0
x = a + b + c
if x > 9:
node = Node(x%10)
c = 1
else:
node = Node(x)
c = 0
node.next = prev
prev = node
if node1 is not None:
node1 = node1.next
if node2 is not None:
node2 = node2.next
if c == 1:
node = Node(1)
node.next = prev
return node
def sum_list(node1, node2):
node1 = reverse_list(node1)
node2 = reverse_list(node2)
return sum_reverse_list(node1, node2)
num1 = [9, 9, 9]
node1 = gen_list(num1)
print_list(node1)
print('+')
num2 = [1, 2, 3]
node2 = gen_list(num2)
print_list(node2)
print('-----')
print_list(sum_list(node1, node2))
///#include <iostream>
struct Node {
int data;
Node* next;
explicit Node(int d) : data{d}, next{nullptr} {}
Node(int d, Node* n) : data{d}, next{n} {}
};
int getNum(Node* n) {
int num = 0;
auto curr = n;
while(curr){
num = num*10 + curr->data;
curr = curr->next;
}
return num;
}
Node* getSum(Node* a, Node* b){
int a_d = getNum(a);
int b_d = getNum(b);
auto sum = a_d + b_d;
Node* head = nullptr;
while(sum){
auto node = new Node(sum % 10, head);
head = node;
sum = sum / 10;
}
return head;
}
void print(Node* n)
{
auto curr = n;
while(curr) {
std::cout << curr->data << " -> ";
curr = curr->next;
}
std::cout << "NULL\n";
}
int main(){
auto n3 = Node(2);
auto n2 = Node(3, &n3);
auto n1 = Node(4, &n2);
auto m3 = Node(3);
auto m2 = Node(9, &m3);
auto m1 = Node(5, &m2);
print(getSum(&n1, &m1));
return EXIT_SUCCESS;
}\\\
#include <iostream>
struct Node {
int data;
Node* next;
explicit Node(int d) : data{d}, next{nullptr} {}
Node(int d, Node* n) : data{d}, next{n} {}
};
int getNum(Node* n) {
int num = 0;
auto curr = n;
while(curr){
num = num*10 + curr->data;
curr = curr->next;
}
return num;
}
Node* getSum(Node* a, Node* b){
int a_d = getNum(a);
int b_d = getNum(b);
auto sum = a_d + b_d;
Node* head = nullptr;
while(sum){
auto node = new Node(sum % 10, head);
head = node;
sum = sum / 10;
}
return head;
}
void print(Node* n)
{
auto curr = n;
while(curr) {
std::cout << curr->data << " -> ";
curr = curr->next;
}
std::cout << "NULL\n";
}
int main(){
auto n3 = Node(2);
auto n2 = Node(3, &n3);
auto n1 = Node(4, &n2);
auto m3 = Node(3);
auto m2 = Node(9, &m3);
auto m1 = Node(5, &m2);
print(getSum(&n1, &m1));
return EXIT_SUCCESS;
}
LinkedList<Integer> addTwoIntegers(LinkedList l1, LinkedList l2){
ArrayList<Integer> result = new ArrayList<>();
Iterator<Integer> iterator1 = l1.descendingIterator();
Iterator<Integer> iterator2 = l2.descendingIterator();
int rest = 0;
while (iterator1.hasNext() && iterator2.hasNext()){
int d1 = iterator1.next();
int d2 = iterator2.next();
result.add((d1 + d2 + rest)%10);
rest = (d1 + d2)/10;
}
while (iterator1.hasNext()){
int d1 = iterator1.next();
result.add((d1 + rest)%10);
rest = ((d1 + rest))/10;
}
while (iterator2.hasNext()){
int d2 = iterator2.next();
result.add((d2 + rest)%10);
rest = ((d2 + rest))/10;
}
if (rest != 0)
result.add(rest);
Collections.reverse(result);
return new LinkedList<>(result);
}
public static LinkedList<Integer> addTwoIntegers(LinkedList l1, LinkedList l2){
ArrayList<Integer> result = new ArrayList<>();
Iterator<Integer> iterator1 = l1.descendingIterator();
Iterator<Integer> iterator2 = l2.descendingIterator();
int rest = 0;
while (iterator1.hasNext() && iterator2.hasNext()){
int d1 = iterator1.next();
int d2 = iterator2.next();
result.add((d1 + d2 + rest)%10);
rest = (d1 + d2)/10;
}
while (iterator1.hasNext()){
int d1 = iterator1.next();
result.add((d1 + rest)%10);
rest = ((d1 + rest))/10;
}
while (iterator2.hasNext()){
int d2 = iterator2.next();
result.add((d2 + rest)%10);
rest = ((d2 + rest))/10;
}
if (rest != 0)
result.add(rest);
Collections.reverse(result);
return new LinkedList<>(result);
}
LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}
//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}
for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;
if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
res.addFirst(temp3);
}
if(carry > 0)
res.addFirst(carry);
return res;
}
LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}
//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}
for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;
if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
res.addFirst(temp3);
}
if(carry > 0)
res.addFirst(carry);
return res;
}
static LinkedList<Integer> addList(LinkedList<Integer> num1, LinkedList<Integer> num2)
{
LinkedList<Integer> res = new LinkedList<Integer>();
LinkedList<Integer> shorter = new LinkedList<Integer>();
LinkedList<Integer> longer = new LinkedList<Integer>();
int carry = 0;
int maxlen,minlen;
if(num1.size() >= num2.size())
{
maxlen = num1.size();
minlen = num2.size();
shorter = num2;
longer = num1;
}
else
{
maxlen = num2.size();
minlen = num1.size();
shorter = num1;
longer = num2;
}
//Pad shorter list to same length by adding preceeding 0
int diff = maxlen - minlen;
for(int i=0; i<diff; i++)
{
shorter.addFirst(0);
}
for(int i=maxlen-1; i>=0; i--)
{
int temp1 = longer.get(i);
int temp2 = shorter.get(i);
int temp3 = temp1 + temp2 + carry;
carry = 0;
if(temp3 >= 10)
{
carry = (temp3/10)%10;
temp3 = temp3%10;
}
res.addFirst(temp3);
}
if(carry > 0)
res.addFirst(carry);
return res;
}
If the question does not specifically ask to use LinkedList and do the math, you can simply convert it to string -> integer -> string -> list
LinkedList<Integer> first = new LinkedList<>();
first.addFirst(4);
first.addFirst(9);
first.addFirst(3);
first.addFirst(1);
System.out.print("first: " + first);
System.out.println();
String firstString = first.toString().replaceAll("\\[", "").replaceAll("\\]", "").replaceAll(", ", "");
System.out.print("firstString: " + firstString);
System.out.println();
Integer firstInt = Integer.parseInt(firstString);
LinkedList<Integer> second = new LinkedList<>();
second.addFirst(8);
second.addFirst(1);
second.addFirst(3);
System.out.print("second: " + second);
System.out.println();
String secondString = second.toString().replaceAll("\\[", "").replaceAll("\\]", "").replaceAll(", ", "");
System.out.print("secondString: " + secondString);
System.out.println();
Integer secondInt = Integer.parseInt(secondString);
Integer resultInt = firstInt + secondInt;
System.out.print("resultInt: " + resultInt);
System.out.println();
String resultString = resultInt.toString();
System.out.print("resultString: " + resultString);
System.out.println();
LinkedList<Integer> resultIntList = new LinkedList<Integer>();
for(char number: resultString.toCharArray())
{
resultIntList.add(Integer.parseInt(String.valueOf(number)));
}
System.out.print("resultIntList: " + resultIntList);
System.out.println();
void Ch1LinkedLists::add2SingleLinkedLists(std::forward_list<int> &l1, std::forward_list<int> &l2, std::forward_list<int> &final)
{
int sum1 = 0;
for (auto it1 = l1.begin(); it1 != l1.end(); it1++) {
sum1 *= 10;
sum1 += *it1;
}
int sum2 = 0;
for (auto it2 = l2.begin(); it2 != l2.end(); it2++) {
sum2 *= 10;
sum2 += *it2;
}
int sum = sum1 + sum2;
int carry = 0;
while (sum) {
final.push_front(sum % 10);
sum = sum / 10;
}
var sumNormalizedLinkedListNumbers = (a, b) => {
if(a == null && b == null)
return null
if(a == null)
return b
if(b == null)
return a
const currentDigitSum = a.value + b.value
const restSums = sumNormalizedLinkedListNumbers(a.next, b.next)
const nextDigitSum = restSums == null ? null : restSums.value
if(nextDigitSum == null || nextDigitSum < 10) {
return {
value: currentDigitSum,
next: restSums
}
}
return {
value: currentDigitSum + 1,
next: {
value: nextDigitSum % 10,
next: restSums.next
}
}
}
var getLengthOfLinkedList = linkedList => { // O(n)
if(!linkedList)
return 0
return 1 + getLengthOfLinkedList(linkedList.next)
}
var prependLinkedListWithZeros = (linkedList, numberOfZeros) => { // O(n)
while(numberOfZeros > 0) {
linkedList = {
value: 0,
next: linkedList
}
numberOfZeros--
}
return linkedList
}
// main function , it normalizes numbers, calls sumNormalizedNumbers and checks if first digit should be prefixed
var sumLinkedListNumbers = (a, b) => {
const lengthOfA = getLengthOfLinkedList(a) // O(n)
const lengthOfB = getLengthOfLinkedList(b) // O(n)
const maxLength = Math.max(lengthOfA, lengthOfB)
let normalizedA = a
if(lengthOfA < maxLength)
normalizedA = prependLinkedListWithZeros(a, maxLength - lengthOfA) // O(n)
let normalizedB = b
if(lengthOfB < maxLength)
normalizedB = prependLinkedListWithZeros(b, maxLength - lengthOfB) // O(n)
const result = sumNormalizedLinkedListNumbers(normalizedA, normalizedB) // O(n)
if(result.value < 10)
return result
return {
value: 1,
next: {
value: result.value % 10,
next: result.next
}
}
}
void addTwoLinkedListIntegers() {
LinkedList<Integer> result = new LinkedList<Integer>();
LinkedList<Integer> first = new LinkedList<Integer>();
first.addFirst(3);
first.addFirst(2);
first.addFirst(1);
LinkedList<Integer> second = new LinkedList<Integer>();
second.addFirst(7);
second.addFirst(5);
second.addFirst(4);
second.addFirst(3);
int fSize = first.size();
int sSize = second.size();
int diff;
/* Prepend the zeros to match the digits count */
if (fSize < sSize) {
diff = sSize - fSize;
for (int i=0; i<diff ; i++)
first.addFirst(0);
}
else if (sSize < fSize) {
diff = fSize - sSize;
for (int i=0; i<diff ; i++)
second.addFirst(0);
}
int rem = 0;
int idx = first.size()-1;
for (int i=idx; i>=0; i--) {
int val = first.get(i)+second.get(i)+rem;
if (val > 9) {
result.addFirst(val%10);
rem = val/10;
} else {
result.addFirst(val);
rem=0;
}
}
System.out.println(result.toString());
}
Here is a recursive python code
the idea is to get the length of each of list
s1 is the length of l1(list1), s2 is the length of l2(list2)
the function is passed with the lengths
add_list_recursive(l1, l2, s1, s2)
Till the point s1>s2, only l1 is moved
after the point s1==s2, both are moved,
at each step the sum of the value of nodes(if s1>s2, only l1 is available) is taken with the carry from previous call
new val and carry is calculated
the new list is progressively created by appending the node from previous call
class Node:
def __init__(self,val):
self.val = val
self.next = None
def __repr__(self):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
class Llist:
def __init__(self):
self.head = None
self.tail = None
def insert(self, val):
node = Node(val)
if not self.head:
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True
def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
def add_list(l1, l2):
if not l1 or not l2:
return l1 or l2
s1 = 0
head = l1
while(head):
s1+=1
head=head.next
s2=0
head=l2
while(head):
s2+=1
head=head.next
head,carry = add_list_recursive(l1, l2, s1, s2)
if carry > 0:
node = Node(1)
node.next = head
head = node
return head
def add_list_recursive(l1, l2, s1, s2):
if s2>s1:
return add_list_recursive(l2, l1, s2, s1)
if s1>s2:
rlist, carry = add_list_recursive(l1.next, l2, s1-1, s2)
temp_val = l1.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
else:
carry = 0
rlist = None
if s1>1:
rlist,carry = add_list_recursive(l1.next, l2.next, s1-1, s2-1)
temp_val = l1.val + l2.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
llist1 = Llist()
llist1.insert(9)
llist1.insert(2)
llist1.insert(3)
llist1.insert(4)
llist1.insert(5)
print(llist1)
llist2 = Llist()
# llist2.insert(9)
# llist2.insert(2)
# llist2.insert(3)
# llist2.insert(4)
print(llist2)
print(add_list(llist1.head,llist2.head))
Here is a recursive solution in python
class Node:
def __init__(self,val):
self.val = val
self.next = None
def __repr__(self):
head = self
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
class Llist:
def __init__(self):
self.head = None
self.tail = None
def insert(self, val):
node = Node(val)
if not self.head:
self.tail = self.head = node
else:
self.tail.next = node
self.tail = node
return True
def __repr__(self):
head = self.head
string = ""
while(head):
string += str(head.val) + ','
head = head.next
return string
def add_list(l1, l2):
if not l1 or not l2:
return l1 or l2
s1 = 0
head = l1
while(head):
s1+=1
head=head.next
s2=0
head=l2
while(head):
s2+=1
head=head.next
head,carry = add_list_recursive(l1, l2, s1, s2)
if carry > 0:
node = Node(1)
node.next = head
head = node
return head
def add_list_recursive(l1, l2, s1, s2):
if s2>s1:
return add_list_recursive(l2, l1, s2, s1)
if s1>s2:
rlist, carry = add_list_recursive(l1.next, l2, s1-1, s2)
temp_val = l1.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
else:
carry = 0
rlist = None
if s1>1:
rlist,carry = add_list_recursive(l1.next, l2.next, s1-1, s2-1)
temp_val = l1.val + l2.val + carry
val, carry = (temp_val,0) if temp_val < 10 else (temp_val-10,1)
node = Node(val)
node.next = rlist
return node, carry
llist1 = Llist()
llist1.insert(9)
llist1.insert(2)
llist1.insert(3)
llist1.insert(4)
llist1.insert(5)
print(llist1)
llist2 = Llist()
# llist2.insert(9)
# llist2.insert(2)
# llist2.insert(3)
# llist2.insert(4)
print(llist2)
print(add_list(llist1.head,llist2.head))
import collections
list1 = collections.deque()
list2 = collections.deque()
final = collections.deque()
list1.append(8)
list1.append(3)
list1.append(1)
list2.append(9)
list2.append(2)
list2.append(1)
list2.append(4)
print(len(list1))
#print(list2)
carry = 0
for i in range(len(list1) if len(list1) > len(list2) else len(list2)):
add = (list1.pop() if (len(list1) > 0) else 0) + (list2.pop() if len(list2) > 0 else 0) + carry
if add >= 10:
carry = add - 9
add = 0
print(carry)
else:
carry = 0
final.appendleft(add)
if (carry):
final.appendleft(carry)
print(final)
- duenytz January 22, 2019