Leonardo Maia Pugliese
Holy Swift

Holy Swift

Odd Even Linked List problem in Swift

Odd Even Linked List problem in Swift

Sharpening our two pointers techniques

Leonardo Maia Pugliese's photo
Leonardo Maia Pugliese
·Jan 5, 2022·

4 min read

Subscribe to my newsletter and never miss my upcoming articles

Hallo vrienden, Leo Hier.

Today we will explore a linked list problem. Linked lists are a very curious data structure because you can have a lot of variants of it. For example you can have a Doubly linked or a singly linked, that means if the nodes of the list have link to next node only or they have a link to the next node and a link to the previous node.

A lot of computer science problems envolves linked lists, a very common example is pagination. When we deal with pagination a very common implementation is using a doubly linked list, this way you can go forward and backward with ease.

No more talking, let's code. But first...

The Painting

The painting is a 1913 art piece called Morning in the Village after Snowstorm from the painter Kazimir Severinovich Malevich. He was a Russian avant-garde artist and art theorist, whose pioneering work and writing had a profound influence on the development of non-objective, or abstract art, in the 20th century.

I chose this painting because it says a lot about connecting things. It's amazing how the painter can connect geometric forms, in this case he has already assimilated the cubism movement, and make us thinking on abstractions of the reality instead of the reality itself.

The problem

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.

You can check the details in the leetcode problem.

So imagine that we have now a linked list and we to rearrange nodes of it. The way we will rearrange is that every node with odd index will be grouped in the left side of the linked list, and the nodes with even index will be grouped in the right side of the linked list.

The image below is the example we are trying to achieve.

Screenshot 2022-01-05 at 08.18.57.png

Implementation

The first thing that pop into my mind is: let's create two pointers, one for the odd linked list and one to the even linked list. After I have those two pointers, I'll traverse the list updating the pointers and in the end I connect the final node of the odd list with the head node of the even list.

The implementation will use two pointers, as many of the linked list solutions uses. The knowledge to manipulate pointers is very important when writing algorithms using linked lists. And that's exactly what we are going to do now:

    func oddEvenList(_ head: ListNode?) -> ListNode? {
        var oddList: ListNode? = head // Mark 1
        var evenList = head?.next // Mark 2
        let evenHead = evenList // Mark 3

        while (evenList != nil && evenList?.next != nil) { // Mark 4
            oddList?.next = evenList?.next // Mark 5
            oddList = oddList?.next // Mark 5

            evenList?.next = oddList?.next // Mark 6
            evenList = evenList?.next // Mark 6
        }

        oddList?.next = evenHead // Mark 7

        return head
    }

Explaining the algorithm:

  1. Mark 1 - we create the odd list first element.
  2. Mark 2 - we get the next element of the odd list, that can only be an even to be the start of the event list.
  3. Mark 3 - we save the head of the even list so we can reference that in the end of the algorithm.
  4. Mark 4 - Now we start to traverse the linked list. We will traverse until the point that the even list is not nil, because if it's nil we just will add it in the end anyway and the next of even list is also not nil because if is doesn't worth to change the pointers because we will add it in the end of the algorithm anyway.
  5. Mark 5 - Now we will start to update our odd list pointers. The next odd list node should be the next of the current even list. And after that we update the odd list pointer itself to be that node. We do this to continuing traversing the linked list. If we don't update the oddList pointer it will always point to the same node.
  6. Mark 6 - Is the exactly the same logic that we did in the Mark 5 but now for the even list. The next of the new oddList should be the next of the current evenList and the evenList itself becomes the updated with it next.
  7. Mark 7 - As a final step we connect the last node of the oddList to the head node of the evenList, remember we were updating it on each traverse cycle.

And that's it!

Summary

Today we analysed a very nice algorithm that uses two pointers to reconnect all the linked list nodes in an arbitrary order.

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