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
# Linked Lists

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

## 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
## Reversing a Singly Linked List

Introduction
Many people have asked me to explain the dynamics of how the reversing of a singly linked list works, when we do not have the liberty of creating a new linked list, may be due to limitation of memory.
The Idea behind Reversing a Singly Linked List
The idea is to iterate through the complete linked list and maintain three pointers as listed below:
Pointer to the head of un reversed list headOfUnReversedLL.
Pointer to the head of reversed list headOfReversedLL.
Pointer to the node to be reversed nodeToReverse.
In each iteration we follow the below four steps:
The h...

Read More
## Merging two Sorted Singly Linked List

Introduction - Merging two Sorted Singly Linked List
This question is mostly asked in interviews and hence I thought of writing few possible solutions to the same. I also asked the same question on stackoverflow.com. You can visit the link here
Problem Statement
You have two singly linked lists that are already sorted, you have to merge them and return the head of the new list without creating any new extra nodes. The returned list should be sorted as well
The method signature is:
[crayon-587ddadbd0b21713555539/]
Node class is below:
[crayon-587ddadbd0b2d788699893/]
Solution
There c...

Read More