6. Reverse LL recursive - easiest #

Created Saturday 18 January 2020

In the two approaches before, we had o(n^2^) and another was returning two values using a public class.

• We observe that for LLs, even after the reversing of the right side part, the ACR’s head’s next still has the rLL’s lastnode. So we don’t need to store it.
• Doubt? Okay, but how do we ensure that the first element points to NULL.

This is very easy to solve, as the ACR’s node has the address of the lastnode of the rLL, we don’t mind the lastnode pointing to NULL. i.e at every step coming back we have a complete LL, and we have the last node pointing to NULL. When this happens on the oldest ACR, we have the first point to NULL. So the list is reversed. Time O(n), S.C: O(n)