Linked List, common problems #️⃣2️⃣

Table of Contents

🌎🧭🌝
#

El mundo vira sin saber donde se mete

Hey everyone! In this post, we’re wrapping up our exploration of linked lists! We covered a lot of ground with linked lists, and I hope you’ve got a solid understanding. But enough talking, let’s get some practice in!

If you need a refresher on anything linked list-related, don’t hesitate to revisit the previous posts. Now, to solidify your newfound knowledge, we’ll tackle 3 more linked list problems!

Alright, are you ready to put your linked list skills to the test? Let’s dive into these problems!

#4 Problem, Find Kth Node From End 🛫🛬
#

The goal is to find the k-th node from the end of a linked list without calculating the total length of the list. This approach is more space-efficient, especially for very long linked lists.

To solve this problem we are gonna use the two Pointer Approach:
#

Initialize two pointers: *fast: This pointer will move k nodes ahead initially. *slow: This pointer starts at the head of the linked list.
Move fast pointer k nodes ahead:

Iterate fast pointer k positions ahead, checking if it reaches the end of the list (null). If it does before k steps, the list has fewer than k nodes, and the function can return an error or None.

Move both pointers together:

Once fast is k nodes ahead, start moving both fast and slow one node at a time.

slow reaches the k-th node from the end:

When fast reaches the end of the list (null), slow will be pointing to the k-th node from the end of the linked list.

So why it works :
#

By the time fast reaches the end, slow has moved k positions ahead from the head, making it point to the k-th node from the end. Here’s the breakdown of the logic 🧐: Imagine the linked list has 8 nodes and you want to find the 3rd node from the end 🛫🛬. Move fast pointer 3 nodes ahead (reaches the 4th node). Now, start moving both pointers together. When fast reaches the end (8th node), slow will be at the 5th node (which is the 3rd node from the end).

Code
#

class LinkedList:

    #   previous code

    def find_kth_from_end(self, k) -> any:
        """
        This method return the Kth node from the end of the linked list 

        Return
            Node
        """  
        slow = fast = self.head

        for _ in range(k):
            if fast is None:
                return None
            fast = fast.next

        while fast:
            slow = slow.next
            fast = fast.next
        
        return slow

#5 Problem, Removing Duplicates from a Linked List 💼
#

We’ll tackle how to remove duplicate nodes from a singly linked list containing integers. We’ll achieve this using a set, which offers efficient lookups to determine if an element has already been encountered.

Approach:
#

Initialize an empty set: This set will store the unique values seen so far while traversing the linked list.
Iterate through the linked list: Use a loop to iterate through each node in the list.
Check for duplicates in the set:

For the current node, check if its data value exists in the set.

If the value is not in the set, it’s unique. Add this value to the set and proceed to the next node.
If the value is in the set, it’s a duplicate. In this case, remove the current duplicate node. At this point you know how to remove any duplicate node, so we skip the explanation of this post

Benefits of using a Set 🦖:
#

Efficient lookups 🔬: Sets provide constant time lookups for element existence, which makes checking for duplicates efficient.
Space complexity ⏱️: The set typically uses space proportional to the number of unique elements encountered, making it space-efficient for scenarios with many duplicates.

Code
#

class LinkedList:

    #   previous code

    def remove_duplicates(self):
        """
        This method detect if the linked list contain a loop 

        Return
            Bool
        """  
        values = set()
        previus = None
        current = self.head

        while current:
            if current.value in values:
                previus.next = current.next
                self.length -= 1
            else:
                values.add(current.value)
                previus = current
            current = current.next

#6 Problem, Removing Duplicates from a Linked List 💼
#

The last ONE! 🍾

implement a method named reverse_between within a linked list class. This method takes two integers, start_index and end_index, as arguments. Its task is to reverse the order of nodes in the linked list, starting at the node with index start_index and ending at the node with index end_index (inclusive)

Approach:
#

Base Case: It checks if the list has less than two elements (length <= 1) and exits if true, as there’s nothing to reverse.
Helper Node: It creates a temporary help_node with a value of 0 and sets its next pointer to the head of the actual list. This node helps in maintaining the beginning of the non-reversed portion.
Iterate to Start Index: It uses a loop to iterate start_index times using previous_node to reach the node before the starting position of the reversal.
Current Node: It sets current_node to the node at the start index (which will be reversed).
Reverse Sublist: It iterates (end_index - start_index times) to reverse the linked list portion between start_index and end_index:

node_to_move: Stores the next node of the current node.
current_node.next: This points to the node after the reversed section.
node_to_move.next: This is set to the current previous_node.next to insert the moved node at the beginning of the reversed portion.
previous_node.next: This is set to node_to_move to update the reversed portion’s starting point.

Update Head: Finally, it updates the head of the list to point to the help_node.next, which is now the beginning of the entire list after the reversal.

Code
#

class LinkedList:

    #   previous code

    def reverse_between(self, start_index, end_index):
        """
        This method reverse elements between a start and end index 

        Return
            None
        """  

        if self.length <= 1:
            return
        
        help_node       = Node(0)
        help_node.next  = self.head
        previous_node   = help_node

        for _ in range(start_index):
            previous_node.next

        current_node = previous_node.next

        for _ in range(end_index - start_index):
            node_to_move        = current_node.next
            current_node.next   = node_to_move.next
            node_to_move.next   = previous_node.next
            previous_node.next  = node_to_move        

        self.head = help_node.next

The song of the post
#

We finish a section of the blog, to celebrate this is necessary to place one of my favourite songs of all times.

🌎🧭🌝
#

Click here to listen

Una tormenta solar
Quemándonos el costado
Moviéndonos hasta lograr
No estar en ningún lado
La luna, la luna
La luna que guía y encandila
Y el corazón que finge decisión
Pero vacila.
La noche cumple solo lo que no promete
La brújula se mueve
Estamos en 1987

Reír y reír y reír
En el eco del abismo
La lógica de confundir
Espejo y espejismo
La luna, la luna,
La luna lamiéndonos la fiebre
Y el corazón que solo se encuentra
Si antes se pierde.
El mundo vira sin saber donde se mete
La brújula se mueve
Estamos en 1987

— 1987 - Campo ft. Jorge Drexler

🌎🧭🌝 #

#4 Problem, Find Kth Node From End 🛫🛬 #

To solve this problem we are gonna use the two Pointer Approach: #

So why it works : #

Code #

#5 Problem, Removing Duplicates from a Linked List 💼 #

Approach: #

Benefits of using a Set 🦖: #

Code #

#6 Problem, Removing Duplicates from a Linked List 💼 #

Approach: #

Code #

The song of the post #

🌎🧭🌝 #

🌎🧭🌝
#

#4 Problem, Find Kth Node From End 🛫🛬
#

To solve this problem we are gonna use the two Pointer Approach:
#

So why it works :
#

Code
#

#5 Problem, Removing Duplicates from a Linked List 💼
#

Approach:
#

Benefits of using a Set 🦖:
#

Code
#

#6 Problem, Removing Duplicates from a Linked List 💼
#

Approach:
#

Code
#

The song of the post
#

🌎🧭🌝
#