3 Algorithms Per Week

Given a number (n), find all the prime numbers smaller than or equal to n. Sieve of Eratosthenes is one of the most efficient algorithms to find all prime numbers smaller than or equal to n. when n is smaller than 10 million or so. A prime number is a number divisible only by itself and one. Example 13, 17, 7, etc. Algorithm: We use a boolean array which has a size of N i.e. arr[1...n]. We start from 2 and make the array value false for all the indexes which are multiples of 2. credits: GeeksForGeeks We find the next element in the array which is True. This is our next prime number i.e. 3. We make the array value false for all the indexes which are multiples of 3. credits: GeeksForGeeks And then again find the next True value which is the next prime number. We repeat this process until we reach n. At the end, all the values in the array which are True have a prime index value. Optimization: Rather than running the loop for prime p from (2*p...

Given, a pointer to the head of a singly linked list, sort the linked list such that all nodes are arranged in non-decreasing order of their node values. Sorting a linked list Algorithm: We have already discussed Merge Sort on arrays . The approach will be similar in the case of linked lists as well. 1. Recursively Divide the list into two havles 2. Sort the two smaller halves. 3. Merge the two halves back together. We have also discussed how to find the middle node in a singly linked list .  The find middle node function will help us divide the linked list into two halves. Once the linked list is divided into two halves, we need to sort the sub-linked lists and merge them back together using the merging function. We will use a dummy node method to store the intermediate merged linked list whose head will be returned as result. Code in Python:  # Python program to perform Merge Sort on a Signly linked list # Node class class Node: # Constructor to i...

Given the head of a singly linked list, segregate even value nodes with odd value nodes such that all the even value nodes come before all the odd value nodes in the order of their appearance. Segregate Even and Odd value nodes Algorithm: Remember the pivot logic we used in QuickSort ? In QuickSort the pivot value was used to separate all the values which are smaller than pivot towards the left of the pivot and all the values greater than pivot value towards the right of the pivot. We will use a similar logic here. 1. Find the first even value node. 2. Bring this node to the start of the linked list. (Call it pivot) 3. Find the next even value node. 4. Insert this node after the pivot and increment pivot one node ahead. 5. Repeat this until we reach Null or None. The algorithm states to bring the first even value node to the start of the linked list and make a pointer pivot point towards it. Whenever we find an even value node, we need to link the previous node to ...

Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in alternate groups of K nodes. Reversed alternate K nodes in a linked list Algorithm: We discussed Reversing a linked list in groups of K nodes in the previous post. The logic here is also the same, the only difference is that before the recursive call we traverse K more nodes so that we can skip them. """ Perform the skip after reversing the previous k nodes """ count = 0 # traverse the k nodes to be skipped while current is not None and count < k-1: current = current.next count += 1 Code in Python: # Python program to alternately reverse a linked list in group of given size k # Node class class Node: # Constructor to initialise data and next def __init__(self, data=None): self.data = data self.next = None class SinglyLinkedList: # Constructor to initialise head def __init__(self): self...

Given a pointer to the head of a Singly linked list, our objective is to reverse the linked list in groups of K nodes. Reversing linked list in groups of 3 nodes Algorithm: Reversing K nodes can use the reverse linked list algorithm we discussed in an earlier post. Initialize: count = 0 current = head next = prev = None 1. while current does not become Null and count < k do: 2. reverse the linked list 3. end while 4. If there are further nodes left in the linked list 5. recursively call reverse linked list for next node 6. and store the returned value in head of the current call 7. return prev at each call as new head The algorithm is fairly simple, keep on reversing the linked list until k nodes are reversed or the linked list end. As you can see in the above diagram: After reversing A-B-C to C-B-A A that was earlier the head of the k nodes group should now point to the next reversed k nodes head which is F. To do this we have to first rever...

Given a pointer to the head of a singly linked list, whose last Node points to an intermediate node of the linked list, find and remove the cycle if it exists. As you can see in the image above, Node E's next pointer points to Node C. If we remove the cycle it will point to Null which is expected by a singly linked list. The problem can be divided into two parts: 1. Finding if the cycle exists 2. Removing the cycle Finding the cycle: We discussed Finding if a cycle exists in a linked list in our previous post. We would tweak the same function to remove the cycle. Removing the cycle: Once the fast pointer equals the slow pointer, there are two methods to remove the cycle: Method 1:  1. Count number of nodes present in the loop. Let the count be k. 2. Keep slow on the head and fast on the kth node from head. 3. Move both pointers at the same pace. 4. Stop the fast node when fast.next becomes equal to slow. 5. Make fast.next = None To count the number of nod...