Iteratively Reverse Linked List in Swift

Hallo vrienden, Leo hier. Today’s topic is how to Iteratively Reverse Linked List in Swift and how to reverse linked lists can be useful for you.

This post will be very brief and very important to all involved in algorithms. Reversing Linked Lists is a 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 caused a lot of discussion on 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 the need to know just things that you will ever use in your day-to-day job. Despite all of the controversy about asking about code challenges in interviews or not, I think this is a cool algorithm to study.

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

Let’s code! But first…

Painting of The Day

I choose the 1884 piece called Bathers at Asnières from Georges Pierre Seurat. It has an 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 stops to fight against each other about if algorithms are useful or not, we can all gather at the riverside and just chill out together.

The problem – Iteratively Reverse Linked List in Swift

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. With 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. Then 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 go 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 inverted 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 the last iteration will be pointing always to nil because we replace it with the text of the last current node that is always nil.

And we are done!

Next Studies on Swift Algorithms

Now you know how to reverse a linked list, a tree problem could help you understand more about recursion right? Check this article about showing only the right side of a tree data structure and evolving your recursive skills.

The sliding window pattern is a very famous pattern to deal with contiguous data structures like arrays or Strings. You can check this article to learn more about them solving the longest subsequence without repeating characters.

Summary – Iteratively Reverse Linked List in Swift

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

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:

title image