Master Data Structures & Algorithms For FREE at AlgoMap.io!
GregHogg
Congratulations. Now you can get rejected from both Google and Apple after this solution👏👏
rahulchattopadhyay
The problem I think this solution faces in c++ is the length of the 2 linked lists are large enough such that the concatenated number is greater than the range of int. Plus this isn't the optimal solution, we can add the 2 linked lists by using the sum, carry method.
jayraval
All you need to do is loop through all entries and add the two numbers and the carry. Store the result mod 10 in a new list and carry the result divided by 10.
phill
This is definitely NOT the solution the interviewer would be expecting.
oferron
I think there is a much simpler approach for this, rather than converting to lists then again back to linked list.
architjambhule
Solved this years ago. Now I'm itching to solve it again. Traversing through both lists and adding a new nodes with digits sum and carry.
giantbush
you can do this in O(1) space, like wtf is this solution lmaoooo
georgemichel
Traverse a linked list multiplying each number by 10^n where n is your functional 'index' to convert the list to a number, then add 2 numbers. This is constant memory and O(n) time.
dharma
this is brute force, while that's okay, you also need to show the optimal solution
saifahmedkhan
ok usually I'm on your side when people talk shit in the comments, but this solution is pretty bad. It only works for python and that's because python doesn't have a max integer size. Even if your interview is in python any interviewer worth anything would ask you to do this a different way.
tamemister
When I first did this I was like "Haha! I will just implement a double linked list!" and then found this way because I struggeled too hard with the double linked list approach
MalikMehsi
Yeah. I'm just going to iterate over the list with a carry variable like the following, and yes my code assumes the lists are the same length (we didn't see the constraints), but it would be fairly easy to adjust for different sized lists. Also, my solution takes advantage of integer truncation in java for the carry.
int c = 0, t;
Iterator<Integer> i = l1.iterator();
for (int n : l2) {
out.add(c + (t = n + i.next()) % 10);
c = t / 10;
}
System.out.println(out);
dial-upking
Less pythonic solution (but still in python):
L1=[9, 9, 3]
L2=[9, 9, 4, 7]
r=[]
c=0
for i in range(max(len(L1), len(L2))):
a, b = (0, 0)
if (i<len(L1)):
a = L1[i]
if (i<len(L2)):
b = L2[i]
s = a + b + c
c = 0
while (s>9):
c += 1
s -= 10
r.append(s)
if (c>0):
r.append(c)
print(r)
sorin.n
The only thing that is going to go "boom" is the compiler when it tries to convert (which is one of the test cases on Leetcode) into an integer.
grey-senpai
You shouldn't change a linked list to list. Most of the linked list questions can easily be done that way and most likely not the answer the interviewers are looking for
oreoforlife
Create a dummy node,
Node dummy
Take a pointer temp and point it to the dummy node,
Node* temp=&dummy
Take
Carry=0 first
Then
While(l1 || l2)
if(l1==null) l1.val=0
if(l2==null) l2.val=0
val=(l1.val+l2.val+carry)%10
temp.next=new Node(val)
carry = (l1.val+l2.val+carry)/10
l1=l1.next
l2=l2.next
temp=temp.next
if(carry>0)
temp.next=new Node(carry)
return dummy.next
It’s an optimal solution with O(N) time complexity and O(1) space complexity
sajidhasan
Wouldn't it be better to do something like
Carry=0
For n in A:
If B[n]:
Temp=A[n]+b[n]+carry
Result[n]=temp%10
Carry=Temp/10
You then need to account if B has more values than A.
And I know that's not proper for linked lists, but I can't recall the exact syntax for them, this should still work right?
calebkirschbaum
So you can answer all those interview questions in just Python??🤔
temynator
Try to do that in Java... I got many failed test cases.
