Linked Lists

The category contains all posts on linked lists. A child category to Data Structures

Removing Duplicates from Sorted Linked List

Problem Statement You are given a singly sorted linked list, which has repeated elements. The task at hand is to remove the duplicates from the linked list. Here is a diagram to explain the problem statement Solution for Removing Duplicates from Sorted Linked List As the linked list is sorted, if two nodes contain duplicates, they will always be adjacent to each other. Hence, the trick is to Maintain two pointers (Current_Node_Ptr and Next_Node_Ptr). If the Next_Node_Ptr points to a duplicate node, delete the node and advance the Next_Node_Ptr Make the next of Current_No...
Read More

Finding loop in Linked List

Problem Statement You are given a singly linked list which may or may not contain a loop. The task at hand is to find if the loop exists.  Here is a diagrammatic representation of a loop in a singly linked list. [caption id="attachment_3617" align="aligncenter" width="688"] Finding loop in LinkedList[/caption] It is pretty clear that there is a loop which starts at the node 3 and there are 10 nodes which make the loop. In this case we need to print a YES. If it had been a singly linked list without the node 12 connecting to node 3, we would have printed a NO. Approach to Finding loop i...
Read More

Cloning Linked List having Next and Random Pointer

Introduction This question was asked by a colleague, although it seems to be simple at first but with given restrictions like running time and space limitations, it becomes tricky. You need to be good with Linked Lists to crack the right solution. Here we try to define the problem in more detail. Given a Linked List where each node contains two pointers next and random. The next pointer points to the immediate next node and the random pointer points to any random node in the linked list. Clone the linked list and return the head of the clone. There are definitely certain conditions impos...
Read More

Linked List Batch Reversing

Introduction As I am writing this at 2 AM, this is going to be a small post but definitely an interesting one. This is mostly asked in interviews and is related to my previous post for Reversing a LinkedList. Understanding the problem statement Given a singly linked list L and a number k, we need to reverse each batch of k elements in the linked list. Here is a pictorial representation for the same. For the below input linked list and for k equals to 3, you can see the output linked list under it. Each of the triplets are reversed. Approach We need to use our reverse linked list func...
Read More

Adding numbers using Linked Lists

Introduction Adding numbers has always been fascinating and you may think it to be the easiest mathematical operation possible. But believe me many a times that becomes the toughest problem to solve. Let us discuss this in more detail. It is really easy to add two numbers stored in two memory locations. The ALU provides you the option to use the ADD feature and store it on the DATA bus. This is feasible when both the numbers can fit on the DATA bus one at a time. So, what about adding excessively large numbers, I know that the limit of BigInteger, Long, Double etc is too huge. But what if ...
Read More