#include "stdafx.h"
 
const int length = 4;
 
struct Item
{
    char key [length];
    Item * next;
};
 
struct List
{
    Item * first;
    Item * last;
};
 
const int digits = 10;
 
List array [digits];
 
void clear (List & list)
{
    list.first = nullptr;
    list.last = nullptr;
}
 
void clearAll ()
{
    for (int k = 0; k < digits; k++)
        clear (array [k]);
}
 
List queue;
 
void add (List & target, Item * p)
{
    if (target.first == nullptr)
        target.first = p;
    else
        target.last->next = p;
    target.last = p;
    p->next = nullptr;
}
 
void join (List & target, List & source)
{
    if (source.first != nullptr)
    {
        if (target.first == nullptr)
            target.first = source.first;
        else
           target.last->next = source.first;
        target.last = source.last;
    }
}
 
void split (int d)
{
    Item * p = queue.first;
    while (p != nullptr)
    {
        Item * follow = p->next;
        char c = p->key[d];
        int k = c - '0';
        add (array[k], p);
        p = follow;
    }
 
    clear (queue);
    for (int k = 0; k < digits; k++)
        join (queue, array[k]);
}
 
int main()
{
    clear (queue);
    clearAll ();
    // do queue data
    for (int d = length - 1; d > 0; d--)
        split (d);
 
    return 0;
}