Interview Question
Software Engineer in TestsCountry: United States
Interview Type: Written Test
void SortListList(Node **head)
{
int k = 1; // every k pairs of the nodes are sorted at any time;
bool sortCompleted = false;
for (; !sortCompleted; k <<= 1) // double the k on every iteration.
{
Node **h = head;
while (h && *h)
{
Node *first = *h;
Node *second = *h;
for (int i = 0; i < k && second; ++i)
{
second = second->next;
}
if (h == head && !second)
{
sortCompleted = true;
break;
}
Node *result = NULL;
Node *tail = NULL;
int firstRem = k;
int secondRem = k;
while (firstRem && secondRem && first && second)
{
Node **minNode;
int *rem;
if (first->data < second->data)
{
minNode = &first;
rem = &firstRem;
}
else
{
minNode = &second;
rem = &secondRem;
}
Node *toAdd = *minNode;
*minNode = (*minNode)->next;
--(*rem);
if (tail)
{
tail->next = toAdd;
tail = toAdd;
}
else
{
result = tail = toAdd;
}
}
if (firstRem && first)
{
tail->next = first;
}
else
{
tail->next = second;
}
*h = result;
int count = firstRem + secondRem;
while (count && tail->next)
{
tail = tail->next;
}
h = &(tail->next);
}
}
}
void SortListList(Node **head)
{
int k = 1; // every k pairs of the nodes are sorted at any time;
bool sortCompleted = false;
for (; !sortCompleted; k <<= 1) // double the k on every iteration.
{
Node **h = head;
while (h && *h)
{
Node *first = *h;
Node *second = *h;
for (int i = 0; i < k && second; ++i)
{
second = second->next;
}
if (h == head && !second)
{
sortCompleted = true;
break;
}
Node *result = NULL;
Node *tail = NULL;
int firstRem = k;
int secondRem = k;
while (firstRem && secondRem && first && second)
{
Node **minNode;
int *rem;
if (first->data < second->data)
{
minNode = &first;
rem = &firstRem;
}
else
{
minNode = &second;
rem = &secondRem;
}
Node *toAdd = *minNode;
*minNode = (*minNode)->next;
--(*rem);
if (tail)
{
tail->next = toAdd;
tail = toAdd;
}
else
{
result = tail = toAdd;
}
}
if (firstRem && first)
{
tail->next = first;
}
else
{
tail->next = second;
}
*h = result;
int count = firstRem + secondRem;
while (count && tail->next)
{
tail = tail->next;
}
h = &(tail->next);
}
}
}
thanks all but the code is in C and I am not able not understand as I am dn't have working knowledge of pointers.
Bubble sort should do
- sun November 18, 2011