Reversing Linked List In-Place

In this post, I will go through a simple algorithm for reversing a singly-linked list with space complexity of O(1), i.e., in-place.

There are two methods: one with recursive and the other with iterative. To me, it is easier to solve in recursive format first and then apply iterative afterwards.

Let's dig right in!

By the way, I claim that the recursive algorithm actually has space complexity of O(N), since it is recursively called N times, growing up the stack by O(N). With this view, quick sort no longer becomes an in-place algorithm, as it requires O(log N) recursive calls.

To see why I claim this, compare the functions reverse_with_array and reverse_with_function_with_stack(_helper). They pretty much do the same thing, except that in the first case, we create an array (a list, to be exact, but can be easily replaced by an array) whereas in the second case we simply create this array using recursive function stack. In fact, the recursive way costs more in time as well as space complexity.

In any case, these methods all do the work with quite different implementations!