asim.ghaznawi
BAN USERAkshay is right in principle. however, the limit is not on number of nodes. it is rather on data. idea is to set bit flag for already seen values. the maximum we can do in C++ with this scheme is 64bit X 64bit (2d matrix)(unsigned long long) which is 4096. here is how I did it:
void LinkedList::RemoveDuplicates()
{
class IntMap
{
private:
unsigned long long m_Rows;
unsigned long long m_Cols;
public:
IntMap()
{
this->m_Rows = 0;
this->m_Cols = 0;
}
bool Contains(int data)
{
int quotient = (int)floor(data / 63.0F);
int remainder = data % 63;
unsigned long long rowMask = 1 << quotient;
unsigned long long colMask = 1 << remainder;
return (this->m_Rows & rowMask) == rowMask &&
(this->m_Cols & colMask) == colMask;
}
void Set(int data)
{
int quotient = (int)floor(data / 63.0F);
int remainder = data % 63;
unsigned long long rowMask = 1 << quotient;
unsigned long long colMask = 1 << remainder;
this->m_Rows |= rowMask;
this->m_Cols |= colMask;
}
} intMap;
Node* current = this->m_Start;
Node* previous = NULL;
while(NULL != current)
{
if(!intMap.Contains(current->m_Data))
{
intMap.Set(current->m_Data);
previous = current;
current = current->m_Next;
}
else
{
current = this->DeleteNode(current, previous);
}
}
}
LinkedList::Node* LinkedList::DeleteNode(LinkedList::Node* node, LinkedList::Node* previous)
{
if(NULL == node)
{
return NULL;
}
if(this->m_Start == node)
{
this->m_Start = node->m_Next;
}
else if(NULL != previous)
{
previous->m_Next = node->m_Next;
}
Node* next = node->m_Next;
--this->m_Count;
delete node;
return next;
}
Please note that we can extend the data limit by adding another dimension, e.g. 64x64x64. so, the data limit would be extended to 262144 and you can then add another dimension if needed.
- asim.ghaznawi February 16, 2014
here is how I implemented this:
- asim.ghaznawi February 18, 2014