Given a linkedlist, reverse it using both iterative approach and recursive approach.
Firstly, draw out the diagram.
As you can see, you obviously need 3 pointers to store references to the nodes so the linked list does not break. In case you are wondering why, here’s an illustration.
When you flip your pointer references in the linkedlist, at least your next node is still can be referenced by the nxt pointer.
With these understanding, let’s have a very simple linkedlist to begin our actual code
With the linkedlist, we can do either iterative approach or recursive approach for reversing. For iterative, we can use a while loop.
The last prev is just the head of the reversed linkedlist. Hence in essence, I’m returning head of new linkedlist.
As you can see, a while loop can do the job perfectly using 3 pointers. It runs in O(n) time and has space complexity of O(3)≈O(1) time.
However, for the sake of this exercise, we can convert the while loop into tail recursion. Tail recursion is a special type of recursion where you don’t wait for the stack frame to reach the base case before bubbling up. It actually solves a small part of the problem before moving on. And because of this property, the stack frames will be recycled by python and space complexity is constant.
The above code is essentially flipping the current.next pointer at every recursive call, without waiting for the entire stack frame to finish. The space complexity is O(1) and time complexity is O(n).
Happy coding :)
