My software development journey
Given two linked lists, we have to merge them into a single list by alternatively taking one node from each list.We should do this by re-arranging the links and should not create duplicate nodes while merging. For example consider the two lists 1 -> 2 -> NULL3 -> 4 -> NULL The result should look…
Given a single linked list, and an integer k, we need to reverse the linked list in groups of size k. For example consider the following diagram of input and output linked lists for k = 3. There are no tricks involved in the solution for this problem. It is just an implementation challenge where…
Given a sorted linked list, how do we delete duplicate nodes from it?This question is simple and straightforward, we take two pointers, current and next which points the adjacent nodes. In each iteration we compare the values at these two nodes, if they are equal, we delete the node pointed by next and advance the…
Given a single linked list, how do we split it into two halves. For example the list 1->2->3->4 should be divided into 1->2 and 3->4 If the length of the list is odd, add the extra node to first half; so 1->2->3 should be split to 1->2 and 3. This problem can be efficiently solved…
In one of my previous posts, we have seen how a linked list can be sorted using bubble sort approach. In this post we will see how we can sort a linked list using insertion sort algorithm. Like bubble sort this approach will also take O(n2) time. Here is the strategy for linked list insertion…
Given a sorted linked list write a program to insert data into it’s correct position. For example consider the following linked list 1 -> 3 -> 4 -> 5 Inserting 2 should change the list to 1 -> 2 -> 3 -> 4 -> 5 Inserting 0 should change it to 0 -> 1 ->…
Given a singly linked list, we have to swap the adjacent nodes in it. For example some input/output samples are given below Input output ————————————————- 1->2->3->4->X 2->1->4->3->X 1->2->3->4->5->X …
Given a singly linked list, how do we reverse it by re-arranging the links? For example if the given linked list is 1 -> 2 -> 3 -> NULL. The output of reverse method should be 3 -> 2 -> 1 -> NULL. The following diagram shows the simple steps to perform the reversal. And…
Given a doubly linked list, how do we reverse it by just re-arranging the pointers? Here is an example of input/output. The following picture depicts how we re-arrange the pointers. Here is the Java implementation.
Given two sorted linked lists, how do we merge them without using any extra space. That means we have to re-arrange the links to form a single sorted linked list. For example let us consider the following two sorted lists as input. 1 -> 3 -> 5 -> 7 2 -> 4 -> 6 ->…