Leonardo Maia Pugliese
Holy Swift

Holy Swift

Reverse...  Reverse Linked List... Linked List : Using Recursion.

Reverse... Reverse Linked List... Linked List : Using Recursion.

Recursive functions are gorgeous.

Leonardo Maia Pugliese's photo
Leonardo Maia Pugliese

Published on Nov 10, 2021

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Hallo alle mensen, Leo hier.

Today we will continue to explore the solution to the legendary interview problem called: Reverse Linked List. We study previously the solution using a 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 you anyone want 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...

The Painting

This painting is a 1888 masterpiece called The Voyage Of King Arthur And Morgan Le Fay To The Isle Of Avalon from 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 remind me the tension and calm about interview processes.

The problem

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 in 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 most of recursive algorithms we have to write the escape condition, in our 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 find the last value and keep that value, that will be our return value. Now we already have the right new head of our algorithm. By the way, if you are a interviewer and asking for this question, if the interviewer struggles, you can start build 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 - When start to solve the recursion, you get current next node and change the next of it to the current node. This is a very important step to understand. Here is heart of the algorithm, because 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 new head. Can you figure out what happens if we don't erase the next reference? We would create a circular reference. E.g. The 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
    }

And we are done!

Summary

Today we could check the 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 algorithm is not the usefulness per se, but the reasoning behind it. When you open your mind for new solutions and new ideas it never returns to the original size.

That's all my people, I hope you liked as I enjoyed write this article. If you want to support this blog you can Buy Me a Coffee or just leave a comment saying hello. You can also sponsor posts and I'm open to writing freelancing! Just reach me in LinkedIn or Twitter for details.

Thanks for the reading and... That's all folks.

credits: image

Did you find this article valuable?

Support Leonardo Maia Pugliese by becoming a sponsor. Any amount is appreciated!

Learn more about Hashnode Sponsors
 
Share this