Interview Question: Linked Lists

[PorquePine]

During an interview today, I was asked how I would go about summing the values of two singly linked lists that contained digits. They also said the lists could be unequal lengths.

I asked if the list was stored backwards, as that's how I learned about it at uni, but they said no, it was stored forward.

I was unable to give an answer, even after they hinted that I should be doing this with a recursive function.

Can anyone help me out with what the solution would have been. This was for a C++ job and I'm hoping that if I ever get called back and I'm able to explain I researched the solution, they might see that as a good sign. Thank you.

[shacktar]

The main problem here is to get the numerical value from the digits stored in the list. You would do this once for each list then simply sum the results.

Essentially, you need to make it to the end of the linked list and then you need to construct the number from the digits as the stack unwinds. You can have the recursive function take two parameters by reference: the current place of the digit (0 for ones place, 1 for tens place, etc.) and the number constructed so far. You can have a "ConstructNumberFromDigits" function which would simply be a helper method to call the recursive function.