Let’s consider 2 approaches to reverse a linked list. Consider the following linked list
1 -> 2 -> 3 -> 4 -> 5
Recursive
Reversing a linked list head -> tail is same as reversing tail and then simply appending head at the end. The base case would be that reversing an empty list is the empty list itself.
Iterative
The recursive apporach requires O(n) space due to non tail-recursive function calls. We can however solve this with O(1) space instead.
1 -> 2 -> 3 -> 4 -> 5
c n
In the above illustration c means current and n means next. The basic idea is that next's next pointer needs to be current. We’ll use a temp pointer to save the existing next->next.
1 <- 2 -> 3 -> 4 -> 5
c n t
After that, we update current and next pointers.
1 <- 2 -> 3 -> 4 -> 5
c n
This process can then continue, let’s jump to the end.
1 <- 2 <- 3 <- 4 <- 5 -> null
c n
The algorithm terminates when curr->next is null and curr gives the head of the newly reversed linked list.