Leonardo Maia Pugliese
Holy Swift

Holy Swift

Iteratively Reverse Linked List in Swift

Iteratively Reverse Linked List in Swift

The Legendary Interview Problem

Leonardo Maia Pugliese's photo
Leonardo Maia Pugliese

Published on Oct 29, 2021

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Hallo vrienden, Leo hier.

This post will be very brief and very important to all involved in algorithms. Reversing Linked List is as legendary challenge as a common place to algorithm students. It's important because it teaches us an important concept: how to deal with pointers. The solution I'll show today will be using two pointers and it's iterative, later on I can post the recursive one. But for the sake of the explanation the iterative one is better.

Also this problem cause a lot of discussion in the interwebz with the motto: "How many times you reversed a linked list in your actual job". One side defends that is important to have knowledge of the internals of all basic computer science structures. The other side defends that need to know just things that you will ever use in your day to day job. Despite all of the controversy about asking code challenges in interviews or not, I think this is a cool algorithm to check.

Today it'll be a very short post but an important one, next week should also be short one because I'm very very busy these days.

Let's code! But first...

The Painting

I choose the 1884 piece called Bathers at Asnières from Georges Pierre Seurat. It has a extensive discussion on it. It's amazing to know that this giant masterpiece wasn't famous until the painter was dead.

He applied to the jury of the Salon of the same year to have the work exhibited there, but the jury rejected it. The Bathers continued to puzzle many of Seurat’s contemporaries, and the picture was not widely acclaimed until many years after the death of the artist at the age of just thirty-one. An appreciation of the painting’s merits grew during the twentieth century, and today it hangs in the National Gallery, London, where it is considered one of the highlights of the gallery’s collection of paintings.

I choose this painting because when everyone stop to fight against each other about if algorithms are useful or not, we can all gather in the riverside and just chill out together.

The problem

Given the head of a singly linked list, reverse the list, and return the reversed list.

In simple words, we create two pointers. One to the head and one to the previous node. The gotcha part of the algorithm is that the first previous node is a nil value, and the first head node is the first value. From that information we just have to keep the next head node from the current head and change the current previous with the head node until the current head is nil. Them we return the previous node because the current head node pointer will be `nil.

You can test the solution on the Leetcode!

The algorithm is very simple and very elegant:

    func reverseList(_ head: ListNode?) -> ListNode? {

        var prevNode: ListNode? = nil // Mark 1
        var headNode = head // Mark 1

        while(headNode != nil) { // Mark 2
            let nextHead = headNode?.next // Mark 3
            headNode?.next = prevNode // Mark 4
            prevNode = headNode // Mark 5
            headNode = nextHead // Mark 6
        }

        return prevNode //Mark 7
    }

Let's going through all the Marks! The example linked list is [1,2,3,4,5].

  1. Mark 1 - We create two pointers here. One pointing to the current head node, another pointing to the first previous node.
  2. Mark 2 - If the head is not nil means that we can start our process to move the pointers around.
  3. Mark 3 - Keep the reference from the next node from the head node, it will be the next head node.
  4. Mark 4 - Here is where we invert the linked list. Instead of the headNode.next points to for example 2, it will point to nil.
  5. Mark 5 - The prevNode pointer now it's pointing to the current head node, this is important because we need to update both of the pointers in each iteration.
  6. Mark 6 - The headNode now is the number 2 and we can start the process all over again.
  7. Mark 7 - Now we have two choices. Return the prevNode or the headNode. The headNode on last iteration will be pointing always to nil because we replace it by the next of the last current node that is always nil.

And we are done!

Summary

This is a very classic algorithm and it is always great go back the foundation of computer science. The elegance and the simplicity of this two pointer algorithm is amazing.

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