Linked List, common problems #️⃣1️⃣

Hi. We have been learning a lot about linked lists. I think it is time to put this knowledge into practice. Why do we do this? 🤔. It’s easy, solving common problems.

#1 Problem, reverse a linked list ↩️

#

This problem is very common in many job interviews, and the concept of the problem is very easy to understand. The problem consists of changing the direction of the reference of every node to the previous one, in other words, reverse the linked list 🤌, I could have said that from the beginning and saved a lot of words. To reverse a linked list we have to follow a specifics steps

Solution

#

1. Create a temporary reference to the current head of the linked list, this reference would be a variable called temp.
2. Change the reference of the tail to the head, and the head to the tail.
3. Set two new variables:

• The variable “after” will be pointing to the next reference of the temp variable. This variable helps us to continue iterating through the list after we switch the reference to the previous node. Do you get why we called after? 😎.
• The variable “before” will be pointing to the previous node to change the reference of the .next to the temp node. When we declare the before variable, we set the value to None

4. Iterate through the linked list, and at this point is where the magic begins. The following steps have to be followed by the book.

• Set the variable after referencing temp.next
• Set the reference of temp.next to “before”
• Set the reference of before to temp
• Set the reference of temp to “after”. And that ’s all. To have a better comprehension of the process we described just before, see the following image.

Code

#

class LinkedList:

    #   previous code

	def reverse(self) -> None:
        """
        Invert the order of the linked list

        Return
            None
        """
        temp        = self.head
        self.head   = self.tail
        self.tail   = temp
        after       = temp.next
        before      = None
        for _ in range(self.length):
            after       = temp.next
            temp.next   = before
            before      = temp
            temp        = after

#2 problem, Find the middle node 🔢

#

This problem involves returning the middle node of a linked list without using the length attribute of our class. If the linked list has an even number of nodes, we should return the first node of the second half of the list.

Solution

#

Before we describe the steps of the solution, it is necessary to understand the approach we will use to find the middle node. Imagine you have 2 cars in a race, the first car that we named “fast” and the second one we named “slow”. The fast car moves twice as fast as the second one. To make a long story short, it’s obvious that the “fast” car will be the first to reach the finish line and, and in that moment when the fast car reaches the “slow” car it would be in the middle of the road. I hope you get it ✌️. So let’s turn this “solution-story” into code.

Create two variables

• Slow. This variable would be referencing the head of the linked list.
• Fast. This variable would be referencing 2 nodes ahead of the slow node. If the head of the linked list is None, return None. Iterate through the linked list until the fast variable references None. Once the fast variable references None, return the slow variable.

To get a better idea of what we are doing, see the next image:

Code

#

class LinkedList:

    #   previous code

	def find_middle_node(self) -> any:
        """
        Return the middle node of a linked list.
        If the linked list has an even number of nodes, 
        return the first node of the second half of the list.

        Return
            Any
        """        
        slow = self.head
        fast = self.head.next

        if self.head == None:
            return None
        
        while fast is not None:
            
            slow = slow.next
            fast = fast.next

            if fast is None:
                return slow
            
            fast = fast.next

        return slow

#3 problem, the linked list has a loop? 🤔 🔄

#

Create a method that can detect the presence of a cycle or loop in a linked list using Floyd’s cycle-finding algorithm, also known as the “tortoise and the hare” algorithm.

Solution

#

The approach of this solution is similar to the previous problem. We set 2 variables, slow and fast. Fast moves 2 nodes ahead of slow. If the linked list doesn’t have a loop, at some point fast will reach None. If the linked list has a loop at some point the references of slow and fast will move through the linked list and these two variables would be pointing at the same node. At this point we detect the loop 🪤

Let’s jump into the code:

Code

#

class LinkedList:

    #   previous code

	def has_loop(self) -> bool:
        """
        This method detect if the linked list contain a loop 

        Return
            Bool
        """    

        slow = self.head
        fast = self.head.next

        if self.head == None:
            return False
        
        while fast is not None and fast.next is not None:
            
            slow = slow.next
            fast = fast.next.next

            if fast == slow:
                return True
            
        return False

The song of the post

#

Click here to listen

Ahí vamos

Déjame atravesar el viento sin documentos
Que lo haré por el tiempo que tuvimos
Porque no queda salida, porque pareces dormida
Porque buscando tu sonrisa estaría toda mi vida

— Sin documentos - Los Rodríguez