zapurza
BAN USER1. Have 3 startptr and endptr representing start and end of the lists.
e.g , start0 will point to start of 0's List
end2 will point to end of 2's List and so on.
2. Traverse the given Linked list and append the nodes to the respective endptr.
3. Make head = startptr of 0's List. Append 1's List to endptr0 and then append 2's List to endptr1.
void
append(Nodeptr * node, Nodeptr * startptr, Nodeptr * endptr)
{
(*node)->next = NULL;
if (*startptr == NULL )
{
*startptr = *node;
*endptr = *node;
return;
}
(*endptr)->next = *node;
*endptr = *node;
}
void
sort012(Nodeptr * headref)
{
Nodeptr ptr = *headref;
Nodeptr start0 = NULL, end0 = NULL, start1 = NULL, start2 = NULL, end1 = NULL,
end2 = NULL;
while (ptr)
{
Nodeptr save_next = ptr->next;
if (ptr->val == 0)
append(&ptr, &start0, &end0);
else if (ptr->val == 1)
append(&ptr, &start1, &end1);
else
append(&ptr, &start2, &end2);
ptr = save_next;
}
*headref = start0;
end0->next = start1;
end1->next = start2;
}
1. Have 3 startptr and endptr representing start and end of the lists.
e.g , start0 will point to start of 0's List
end2 will point to end of 2's List and so on.
2. Traverse the given Linked list and append the nodes to the respective endptr.
3. Make head = startptr of 0's List. Append 1's List to endptr0 and then append 2's List to endptr1.
void
append(Nodeptr * node, Nodeptr * startptr, Nodeptr * endptr)
{
(*node)->next = NULL;
if (*startptr == NULL )
{
*startptr = *node;
*endptr = *node;
return;
}
(*endptr)->next = *node;
*endptr = *node;
}
void
sort012(Nodeptr * headref)
{
Nodeptr ptr = *headref;
Nodeptr start0 = NULL, end0 = NULL, start1 = NULL, start2 = NULL, end1 = NULL,
end2 = NULL;
while (ptr)
{
Nodeptr save_next = ptr->next;
if (ptr->val == 0)
append(&ptr, &start0, &end0);
else if (ptr->val == 1)
append(&ptr, &start1, &end1);
else
append(&ptr, &start2, &end2);
ptr = save_next;
}
*headref = start0;
end0->next = start1;
end1->next = start2;
}
Instead of adding 2s to the end , insert 2s node after head2. Run the loop till you reach head2.
- zapurza September 12, 2012So finally we get,
(head1)0-0-0-1-1-1-(head2)2-2-2