CareerCup

@bhardwaj.ankit
According to the question "Sort them such that all the similar number nodes are cluster together". Don't you think that sorting the series will automatically cluster same numbers together? Do let me know if sorting is the requirement or not.

What do you exactly mean when you say that the similar nodes are clustered together?

If there is no problem in using additional data structure, I would use a treemap <<value, linkedlist of nodes>> . For some value ->key, node will be linked to the linked list. Since it is a treemap, values will be sorted. So after checking all values, and stroing them in the treemap, we can simply output the nodelist in order.

buble sort on linked list

....unless you can find a way with complexity less then O(nlgn).. then merge sort.

Define "similar" please.

what if we use a hashMap
key-->value in the node
value-->linked -list, which contains the nodes with the key value.

Finally, link all the linked-lists in the hashMap together

template <class T>
        void SLList<T>::JoinSimilar()
	{
		LLNode<int> *pCur = pHead;
		if(!pCur || !pCur->pNext) return;
		const int TABLE_SIZE = 10;
		SLList<SLList<int>*> **AggList = new SLList<SLList<int>*>*[TABLE_SIZE]; // hash-table
		for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
		{
			AggList[ind_table] = new SLList<SLList<int>*>; // each element of the table is
		}												// a pointer to the list of lists
		LLNode<int> *pCurTblListNode = NULL, *pTmp = NULL;
		LLNode<SLList<int>*> *pCurTblList = NULL, *pNewTblList = NULL;
		while(pCur)
		{
			pCurTblList = AggList[pCur->iData%10]->pHead; // fill the table element
			while(pCurTblList)
			{
				pCurTblListNode = (pCurTblList->iData)->pHead; // each element is the list of the lists of numbers,
				if(pCurTblListNode->iData == pCur->iData)      // which end with the same digit, e.g.
				{											   // 5->5->5->NULL
					pTmp = pCur->pNext;						   // 35->35->NULL
					pCur->pNext = pCurTblListNode;             // 275->NULL
					(pCurTblList->iData)->pHead = pCur;		   // NULL
					pCur = pTmp;
					break;
				}
				pCurTblList = pCurTblList->pNext;
			}
			if(!pCurTblList)
			{
				pNewTblList = new LLNode<SLList<int>*>;
				pNewTblList->iData = new SLList<int>;
				pNewTblList->pNext = AggList[pCur->iData%10]->pHead;
				AggList[pCur->iData%10]->pHead = pNewTblList;
				(pNewTblList->iData)->pHead = pCur;

				pTmp = pCur->pNext;
				pCur->pNext = NULL;
				pCur = pTmp;
			}
		};
		LLNode<int> *pFisrt = NULL, *pLast = NULL, *pLastTblList = NULL;
		for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++) // join all the lists into one single list
		{                                                           // and then set the head of the base list to the
			pCurTblList = AggList[ind_table]->pHead;                // new joint list
			while(pCurTblList)
			{
				if(!pFisrt)
				{
					pFisrt = (pCurTblList->iData)->pHead;
				}
				pLast = (pCurTblList->iData)->pHead;
				if(pLastTblList)
				{
					pLastTblList->pNext = pLast;
				}
				while(pLast->pNext)
				{
					pLast = pLast->pNext;
				};
				if(pCurTblList->pNext)
				{
					pLast->pNext = ((pCurTblList->pNext)->iData)->pHead;
					pLastTblList = NULL;
				}
				else
				{
					pLastTblList = pLast;
				}
				pCurTblList = pCurTblList->pNext;
			}
		}
		pHead = pFisrt;

		for(int ind_table = 0; ind_table < TABLE_SIZE; ind_table++)
		{
			delete AggList[ind_table];
		}

FOR GODS SAKE, JUST DO AN INSERTION SORT

I think the phrasing 'similar' is intentional. 99 and 999 are similar, but 99, 101, 345, 999 after sorting don't put them together. This is Microsoft. It can't be as simple as sorting.

struct {
int num;
int cluster_number;
struct node* link;
}