Hallo alle mensen, Leo hier. Today’s topic is how to reverse linked list using recursion and how to do that in our custom linked list data structure.
Today we will continue to explore the solution to the legendary interview problem called: Reverse Linked List. We study previously the solution using an iterative technique, now let’s dive into the recursive solution.
Recursion is no joke for me. This is the second hardest subject in algorithms in my honest opinion (the first one is the dreadful dynamic programming, if anyone wants to know ).
But at the same time, I think that recursion algorithms have an unparalleled elegance. How they solve intricate problems using the compiler stack and manipulating pointers in each instance is just a piece of artwork.
No more talking, let’s do it! But first…
Painting of The Day
This painting is an 1888 masterpiece called The Voyage Of King Arthur And Morgan Le Fay To The Isle Of Avalon by Frank William Warwick Topham.
Frank William Warwick Topham, the painter of this piece. I couldn’t find much info about the artist but at least we can read a little bit about his father Francis William Topham here.
I choose this painting because I like the calm vibes of king Arthur even when the kingdom is burning in the background. This reminds me of the tension and calms about interview processes.
The problem – Reverse Linked List Using Recursion
Given the head of a singly linked list, reverse the list, and return the reversed list.
The problem is the same as the last post about it, and you can check your solution on the leetcode website.
The approach now will be iterative. The reasoning about it is pretty much the same, we have to deal with each node pointing to the right place in each iteration.
The algorithm can be described as:
1 – First as in most recursive algorithms we have to write the escape condition. In this case, head is nil or the next node of the head is nil. Either case we just return head.
func reverseList(_ head: ListNode?) -> ListNode? {
guard let head = head, let _ = head.next else { return head } // 1
}
2 – Now traverse recursively the linked list until finding the last value and keep that value, that will be our return value. Now we already have the right new head for our algorithm. By the way, if you are an interviewer and asking for this question, if the interviewer struggles, you can start building up this algorithm asking just to return the right new head for the linked list.
func reverseList(_ head: ListNode?) -> ListNode? {
guard let head = head, let _ = head.next else { return head } // 1
let newHead = reverseList(head.next) // 2
return newHead // 2
}
3 – Starting to solve the recursion, get the current next node and change the next of it to the current node. This is a very important step to understand. Here is the heart of the algorithm. We have the current node and we are fixing the pointer of the next one to point to the current head. The magic is we do this for every node in the linked list, and in the end, we fix all the directions.
func reverseList(_ head: ListNode?) -> ListNode? {
guard let head = head, let _ = head.next else { return head } // 1
let newHead = reverseList(head.next) // 2
let nextNode = head.next // 3
nextNode?.next = head // 3
// this third step can also be head.next?.next = head, I think splitting this is easier to visualise
return newHead // 2
}
4 – Erase the next reference of the current node and return the new head. Can you figure out what happens if we don’t erase the next reference? We would create a circular reference. E.g. node 1 will be pointing to node 2 and node 2 will be pointing to node 1.
func reverseList(_ head: ListNode?) -> ListNode? {
guard let head = head, let _ = head.next else { return head } // 1
let newHead = reverseList(head.next) // 2
let nextNode = head.next // 3
nextNode?.next = head // 3
head.next = nil // 4
return newHead // 2
}
Continue Studying Algorithms
You also need to know what to do with String problems, and one classic problem is described in this article where you will learn how to find the symmetric difference in a String.
Working with stacks is an important tool to have when solving algorithm problems, for example the problem about matching parenthesis explained in this article. Did you know that you can use a stack to solve that problem?
Summary – Reverse Linked List Using Recursion
Today we could check how we build the recursive algorithm to solve a legendary interview problem. I know what you are thinking: Where I would use this in my real life?
Well, that’s the 1 million question. For me, the importance of studying algorithms is not the usefulness per se, but the reasoning behind them. When you open your mind to new solutions and new ideas it never returns to the original size.
That’s all my people, I hope you liked reading this article as much as I enjoyed writing it. If you want to support this blog you can Buy Me a Coffee or leave a comment saying hello. You can also sponsor posts and I’m open to freelance writing! You can reach me on LinkedIn or Twitter and send me an e-mail through the contact page.
Thanks for reading and… That’s all folks.
Credits:
