To solve this problem we will use a recursive approach.
The idea here is that we need to add the list but as we know that addition is only possible when traversing from the end like adding firstly the unit place elements and then carry forwarding to the next place and so on.
This generalized process here we will try to implement using recursion as we are not allowed to reverse the list.
Let's see the solution through an example.
We take the linked lists as 9-8-7-5 and 4-6. On top of each digit the place value of that digit is written in white.
We use stack to understand this problem. It is divided into 2 parts: Going up the stack and Going down the stack.
UP THE STACK(PUSH)
We make a stack and add the most significant digits of both the linked lists along with their place values (digits are denoted in white and place value in red in the figure 3).
Since the place values of "one" and "two" are different they can't be added together. Hence we move towards the lesser significant digits for "one" till the place value of "one" and "two" is the same.
We reach the position shown in figure 4 where the place values are the same.
But we don't start the addition now because we have to start from the least significant digit and move towards the most significant digit.
We move both the pointers forward and push a new level in the stack until they reach null (see figure 5).
We reach the end of our pushing process.
DOWN THE STACK (POP)
Now when we have reached the null position, we are going to return 0 as the carry value. This is our Base Condition.
Now we take the sum of carry and the two digits. Here, the new carry is the ten's digit of the sum. This new carry is returned.
Also, the one's digit of the sum is added first to the resultant linked list.
In our example, 0+5+6=11. Hence ten's digit 1, the new carry is returned and one's digit, 1 is added to the resultant as shown in figure 7.
As 1 is returned to the digits at place value 2, the process is repeated. Our sum =1+7+4=12. Now 1 is the new carry and 2 is added first to the resultant linked list.
As all the digits of the second linked list have been used up, therefore we just include carry and the next digit of the first linked list. So, 1+8=9. Hence, new carry is 0 and 9 is added first to the resultant.
Again, for the greatest significant digit, 0+9=9 is the sum. Hence 0 is returned as carry and 9 is added first.
*Had the carry been more than 0 we would have added that value of carry in the resultant linked list too.
Our final answer hence looks like as shown in figure 9.
Hence our answer is 9921.
Try to write the code for the above explanation yourself. If you face any problems, feel free to refer to the code given below.