


#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;
}